## Permutation and Combination

**Permutation:** Each of the arrangements in a definite order which can be made by taking some or all of a number of things is called a Permutation.

**Combination:** Each of the groups or selections which can be made by taking some or all of a number of things without reference to the order of the things in each group is called a Combination.

**Fundamental Principle Of Counting:**

If an event can occur in ‘m*’* different ways, following which another event can occur in ‘n’ different ways, then the total number of different ways of simultaneous occurrence of both events in a definite order is m × n. This can be extended to any number of events.

Results:

- A Useful Notation : n! = n (n − 1) (n − 2)……… 3. 2. 1 ; n ! = n. (n − 1) !0! = 1! = 1 ; (2n)! = 2n. n ! [1. 3. 5. 7…(2n − 1)] Note that factorials of negative integers are not defined.
- If
^{n}P_{r}denotes the number of permutations of n different things, taking r at a time, then

\(^{\mathrm{n}} \mathrm{P}_{\mathrm{r}}=\mathrm{n}(\mathrm{n}-1)(\mathrm{n}-2) \ldots \ldots(\mathrm{n}-\mathrm{r}+1)=\frac{\mathrm{n} !}{(\mathrm{n}-\mathrm{r}) !} \text { Note that }, \mathrm{n}_{\mathrm{n}}=\mathrm{n} !\) - If
^{n}C_{r}denotes the number of combinations of n different things taken r at a time, then

\(^{\mathrm{n}} \mathrm{C}_{\mathrm{r}}=\frac {\mathrm{n} !}{\mathrm{r} !\left(\mathrm{n}-\mathrm{r}\right) !}=\frac{^{n} \mathbf{P}_{r}}{r !}\) where r ≤ n ; n ∈ N and r ∈ W. - The number of ways in which (m + n) different things can be divided into two groups containing m & n things respectively is: \(\frac {\left(\mathrm{m}+\mathrm{n}\right) !}{\mathrm{m} !\mathrm{n} !}\) If m = n, the groups are equal & in this case the number of subdivision is \(\frac {\left(2n\right) !}{n!n!2!}\); for in any one way it is possible to interchange the two groups without obtaining a new distribution. However, if 2n things are to be divided equally between two persons then the number of ways \(=\frac {(2n)!}{n!n!}\)
- Number of ways in which (m + n + p) different things can be divided into three groups containing m , n & p things respectively is \(\frac {(m+n+p) !}{m!n!p!}\), m ≠ n ≠ p. If m = n = p then the number of groups \(=\frac {(3n) !}{n!n!n!3!}\) . However, if3n things are to be divided equally among three people then the number of ways \(=\frac {(3n)!}{(n!)^{3}}\)
- The number of permutations of
*n*things taken all at a time when*p*of them are similar & of one type, q of them are similar & of ano ther type,*r*o f them are similar & of a third type & the remaining n – (p + q + r) are all different is: \(\frac {n!}{p!q!r!}\) - The number of circular permutations of n different things taken all at a time is ; (n − 1)!. If clockwise & anti−clockwise circular permutations are considered to be same, then it is \(\frac {(n-1)!}{2}\)

Note: Number of circular permutations of n things when p alike and the rest different taken all at a time distinguishing clockwise and anticlockwise arrangement is \(\frac {(n-1)!}{p!}\) - Given n different objects, the number of ways of selecting atleast one of them is ,
^{n}C_{1}+^{n}C_{2}+^{n}C_{3}+…..+^{n}C_{n}= 2^{n}− 1. This can also be stated as the total number of combinations of n distinct things. - Total number of ways in which it is possible to make a selection by taking some or all out of p + q + r +…… things , where p are alike of one kind, q alike of a second kind , r alike of third kind & so on is given by: (p + 1) (q + 1) (r + 1)…….. –1.

(x) Number of ways in which it is possible to make a selection of m + n + p = N things , where p are alike of one kind , m alike of second kind & n alike of third kind taken r at a time is given by coefficient of x^{r}in the expansion of (1 + x + x² +…… + x^{p}) (1 + x + x² +…… + x^{m}) (1 + x + x² +…… + x^{n}).

Note: Remember that coefficient of x^{r}in (1 − x)^{-n}=^{n+r-1}C_{r }(n ∈ N). For example the number of ways in which a selection of four letters can be made from the letters of the word Proportion is given by coefficient of x^{4}in (1 + x + x² + x^{3}) (1 + x + x²) (1 + x + x²) (1 + x) (1 + x) (1 + x). - Number of ways in which n distinct things can be distributed to p persons if there is no restriction to the number of things received by men = p
^{n}. - Number of ways in which n identical things may be distributed among p persons if each person may receive none , one or more things is ;
^{n+p−1}C_{n}. - a.
^{n}C_{r}=^{n}Cn−r ;^{n}C_{0}=^{n}C_{n}= 1;

b.^{n}C_{x}=^{n}C_{y}⇒ x = y or x + y = n

c.^{n}C_{r}+^{n}C_{r-1}=^{n+1}C_{r} ^{n}C_{r}is maximum if :

(a) \(r=\frac {n}{2}\) if n is even.

(b) \(r=\frac{n-1}{2} \text { or } \frac{n+1}{2}\) if n is odd.- Let N = p
^{a}. q^{b}. r^{c}…… where p , q , r…… are distinct primes & a , b , c….. are natural numbers then:

(a) The total numbers of divisors of N including 1 & N is = (a + 1)(b + 1)(c + 1)…..

(b) The sum of these divisors is = (p^{0}+ p^{1}+ p^{2}+…. + p^{a}) (q^{0}+ q^{1}+ q^{2}+…. + q^{3}) (r^{0}+ r^{1}+ r^{2}+…. + r^{c})….

(c) Number of ways in which N can be resolved as a product of two factors is = \(\frac{1}{2}(a+1)(b+1)(c+1) \dots+1\) if N is not a perfect square

\(\frac{1}{2}[(a+1)(b+1)(c+1) \dots+1]\) if N is a perfect square

(d) Number of ways in which a composite number N can be resolved into two factors which are relatively prime (or coprime) to each other is equal to 2^{n-1}where n is the number of different prime factors in N. [ Refer Q.No.28 of Ex−I ] - Grid Problems and tree diagrams.

**Dearrangement:**Number of ways in which n letters can be placed in n directed letters so that no letter goes into its own envelope is \(=n![\frac {1}{2!}-\frac {1}{3!}-\frac {1}{4!}+\ldots\ldots+(-1^{n})\frac {1}{n!}]\) - Some times students find it difficult to decide whether a problem is on permutation or combination or both. Based on certain words/phrases occurring in the problem we can fairly decide its nature as per the following table:
- Problems on Combinations
- Selections, choose
- Distributed group is formed
- Committee
- Geometrical problems

- Problems on Permutations
- Arrangements
- Standing in a line seated in a row
- problems on digits
- Problems on letters from a word