Permutation and Combination Questions, Formulas and Examples

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 ⁿ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 ⁿ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 , ⁿC₁ + ⁿC₂ + ⁿC₃ +…..+ ⁿC_n = 2ⁿ − 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ⁿ).
  Note: Remember that coefficient of x^r in (1 − x)^-n = ^n+r-1C_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⁴ in (1 + x + x² + x³) (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ⁿ.
• 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−1C_n.
• a. ⁿC_r = ⁿCn−r ; ⁿC₀ = ⁿC_n = 1;
  b. ⁿC_x = ⁿC_y ⇒ x = y or x + y = n
  c. ⁿC_r + ⁿC_r-1 = ⁿ⁺¹C_r
• ⁿ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⁰ + p¹ + p² +…. + p^a) (q⁰ + q¹ + q² +…. + q³) (r⁰ + r¹ + r² +…. + 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