# CAT Quant : Permutation and Combination (PnC) – Important Formulas and Concepts

## Fundamental Rule

- The fundamental rule concerning permutation and combination can be stated as follows –
- If one operation can be performed in ‘m’ ways and (when, it has been performed in any one of these ways), a second operation then can be performed in ‘n’ ways, the number of ways of performing the two operations will be m x n.
- This can be extended to any number of operations.
- For Example – If there are three cities A, B and C such that there are 3 roads connecting A and B and 4 roads connecting B and C, then the number of ways one can travel from A to C is 3 x 4, ie., 12.

## Permutations

- A permutation is an arrangement of objects in a specific order.
- Permutation implies “arrangement” or that “order of the items” is important, thus, the words “permutation” and “arrangement” are synonymous and can be used interchangeably.
- The number of permutations of n things taking rat time is denoted by ” \( ^{n}P_r \)” (read as “nPr”) and can be calculated as $$ ^{n}P_r = \frac{n!} {(n-r)!}$$ where n! denotes the factorial of n, which is the product of all positive integers less than or equal to n.

## Combination

- A combination is a selection of objects without regard to the order.
- In combinations, the order in which the items are taken is not considered as long as the specific things are included. The words “combination” and “selection” are synonymous.
- The number of combinations of n things taking r at time is denoted by \( ^{n}C_r (read as nCr) and calculated as $$^{n}C_r = \frac{n!}{r! \cdot (n-r)!} $$ where n! denotes the factorial of n, which is the product of all positive integers less than or equal to n.
- The number of combinations of n dissimilar things taken all at a time is 1.
- Certain Properties of Combinations –
- \( ^{n}C_0 = 1 \)
- \( ^{n}C_1 = ^{n}C_{n-1} = n \)
- \( ^{n}C_r = ^{n}C_{n-r} \)

## Cases under Permutation

**CASE 1 : Number of arrangements of n items of which p are of one type, q are of a second type and the rest are distinct –**- The number of ways in which n things may be arranged taking them all at a time, when p of the things are exactly like one kind, q of them exactly like another kind, r of them exactly like of a third kind, and the rest all distinct is $$ \frac{n!}{(p! \ q! \ r!)} $$

**CASE 2 : Number of arrangements of n distinct items where each item can be used any number of times (i.e., repetition allowed) –**- When selecting items with repetition allowed, each selection can be made independently and has the same number of choices, which is n.
- For r selections, each selection can be made in n ways, resulting in a total of \( n \times n \times n \) … (r times) ways, which simplifies to \( n^r \).
- Thus, the number of permutations of n things taken r at a time with repetition allowed is \( \longrightarrow n^r \).
- Note – When solving questions of such type it is better to grasp the reasoning behind the formula rather than memorizing it directly.

**Total number of combinations **

- Out of n given things, the number of ways of selecting one or more things is where we can select 1 or 2 or 3… and so on n things at a time; hence the number of ways is \( ^{n}C_1+^{n}C_2+^{n}C_3 + … ^{n}C_n \).
- This is called “the total number of combinations” and is equal to \( (2^{n}-1) \) where n is the number of things.
- Also, the Number of ways of selecting one or more items from n given items is $$ 2^{n}-1 $$

## Dividing given items into Groups

**Dividing (p+q) items into two groups of p and q items respectively –**- Out of (p+q) items, if we select p items (which can be done in \( ^{p+q}C_p \) ways), then we will be left with q items, i.e.. we have two groups of p and q items respectively.
- So, the number of ways of dividing (p+q) items into two groups of p and q items respectively is equal to – $$ ^{p+q}C_p = \frac{(p+q)!}{p! \cdot q!}$$
- If p = q i.e., if we have to divide the given items into two EQUAL groups, then two cases arise –
**when the two groups have distinct identity :**- Here, we just have to substitute p=q in the above formula
- The number of ways of dividing 2p items into two equal groups of p each is $$ \frac{(2p)!}{(p!)^{2}} $$ where, the two groups have distinct identity.

**when the two groups do not have distinct identity :**- In the second case, where the two groups do not have distinct identity, we have to divide the above result by 2!.
- The number of ways of dividing 2p items into two equal groups of p each is $$\frac{(2p)!}{2!{(p!)}^{2}} $$ where, the two groups do not have distinct identity.

**Dividing (p+q+r) items into three groups consisting of p, q and r items respectively –**- The number of ways in which (p+q+r) things can be divided into three groups containing p, q and r things respectively is $$ \frac{(p+q+r)!}{p! \cdot q! \cdot r!} $$
- If p = q = r, i.e., if we have to divide the given items into three EQUAL groups, then we have two cases where the three groups are distinct and where the groups are not distinct.
- When the three groups are distinct, the number of ways is $$ \frac{(3p)!}{(p!)^{3}}$$
- When the three groups are not distinct, then the number of ways is $$\frac{(3p)!}{3!(p!)^{3}}$$

## Circular Permutations

- A circular arrangement involves placing objects around a central point in a closed loop, creating a continuous cycle with rotational symmetry.
- In a straight line, arranging n items results in n! permutations, but in a circle, due to rotation, shifting each item by one place doesn’t change the arrangement.
- In a circular arrangement, after fixing one item, the remaining (n-1) items can be arranged in (n-1)! ways.
- Hence, the number of ways in which n distinct things can be arranged in a circular arrangement is $$(n-1)!$$
- The number of circular arrangements of n distinct items is –
- (n-1)! \( \longrightarrow \) if there is difference between clockwise and anticlockwise arrangements
- (n-1)!/2 \( \longrightarrow \) if there is NO DIFFERENCE between clockwise and anticlockwise arrangements

## Sum of all numbers formed from given digits

- If n distinct digits are used to make all the possible n-digit numbers, we get n! numbers.
- If all the possible n-digit numbers using n distinct digits are formed, the sum of all the numbers so formed is equal to $$(n-1)! \times (sum \ of \ the \ n \ digits) \times (11111…..) n \ times$$

## Rank of a word

- The rank of a word is its position when all possible words formed by arranging its letters once are sorted alphabetically.
- For Example – Consider the word “POINT”. Arrange letters in alphabetical order: I, N, O, P, T. Count words preceding “POINT” alphabetically. Words beginning with I: 4! , Words beginning with N: 4! , Words beginning with O: 4! , Words beginning with PI: 3! , Words beginning with PN: 3! . then we arrive at the word ‘POINT’. \( \\ \) There are \( 3 \times 4!+2 \times 3!= 84 \ words\) that precede the word POINT i.e., POINT is the 85th word. \( \\ \) Hence rank of ‘POINT’ is 85.

## The number of diagonals in an n-sided regular polygon

- An n-sided regular polygon has n vertices. Joining any two vertices we get a line of the polygon which are \( ^{n}C_2 \) in number: Of these \( ^{n}C_2 \) lines, n of them are sides.
- Hence diagonals are $$^{n}C_{2}-n=\frac{n(n-3)}{2} $$

## Number of integral solution of the equation x_{1} + x_{2} + … + x_{n} = s

- In general, if x
_{1}+ x_{2}+ … + x_{n}= s where s \( \ge \) n, the number of positive integral solutions is \( \longrightarrow \ ^{s-1}C_{n-1} \) - The number of non-negative integral solutions of the given equation is equal to the number of positive integral solutions of x
_{1}+ x_{2}+ … + x_{n}= (s +n) where s \( \ge \) n, which is \( \longrightarrow \ ^{s+n-1}C{n-1} \)

## Some Additional Points

**Dearrangements –**- Suppose there are n letters and n corresponding addressed envelopes. The numbers of ways of placing these letters into the envelopes such that no letter is placed in its corresponding envelope is often referred as derangements.
- The number of derangements of n objects is given by $$ D(n)=n! {\LARGE[} 1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+….+(-1)^{n}\frac{1}{n!} {\LARGE]} $$

- The total number of ways in which a selection can be made by taking some or all out of p+q+r+…. things where p are like one kind, q like a second kind, r like of a third kind and so on is $$ [\{(p+1)(q+1)(r+1)…..\}-1] $$
- One common conclusion in permutation and combination is $$ ^{n+1}C_{r} = ^{n}C_{r} + ^{n}C_{r-1} \ \ and \ \ ^{n}P_{r} = r_{.}^{n-1}P_{r-1} + ^{n-1}P$$