PERMUTATIONS AND COMBINATIONS - 3 (Simple Applications on ${}^n P_r$ and ${}^n C_r$)
Important Results
1. Total number of selections of one or more objects from $\mathrm{n}$ different objects $={ }^{\mathrm{n}} \mathrm{C} _{1}+{ }^{\mathrm{n}} \mathrm{C} _{2}+\ldots .+{ }^{\mathrm{n}} \mathrm{C} _{\mathrm{n}}=2^{\mathrm{n}}-1$
2. Total number of selections of any number of things from $n$ identical things
$=\left\{\begin{array}{l}(n+1) ; \text { when selection of zero things is allowed } \\ n \quad ; \text { when at least one thing is to be selected. }\end{array}\right.$
3. Total number of selections from $p$ like things, $q$ like things of another type and $r$ distinct things
$=\left\{\begin{array}{l}(\mathrm{p}+1)(\mathrm{q}+1) 2^{\mathrm{r}}-1 \text { (if at least one thing to be selected) } \\ (\mathrm{p}+1)(\mathrm{q}+1) 2^{\mathrm{r}}-2(\text { if none or all cannot be selected) }\end{array}\right.$
4. Total number of selections of $\mathrm{r}$ things from $\mathrm{n}$ different things when each thing can be repeated unlimited number of times ${ }^{n+r-1} C _{r-1}$
5. Total number of ways to divide $n$ identical things among $\mathrm{r}$ persons $={ }^{n+-1} \mathrm{C} _{\mathrm{r}-1}$
Results on distribution
6. Distribution of $n$ things to $r$ boxes
| Given | Condition | Number of ways |
|---|---|---|
| $\mathrm{n}$ distinct things | Empty boxes are allowed | $\mathrm{r}^{\mathrm{n}}$ |
| $\mathrm{r}$ distinct boxes | Empty boxes are not allowed | coefficient of $\mathrm{x}^{\mathrm{n}}$ in $\mathrm{n} !\left(\mathrm{e}^{\mathrm{x}}-1\right)^{\mathrm{r}}$ |
| $\mathrm{n}$ identical things | Empty boxes are allowed | ${ }^{n+r-1} C _{r-1}$ |
| $\mathrm{r}$ distinct boxes | Empty boxes are not allowed | ${ }^{n-1} C _{r-1}$ |
Division of items into groups
7. (i) Groups of unequal size.
- Number of ways in which $(m+n+p)$ items can be divided into unequal groups containing $\mathrm{m}, \mathrm{n}, \mathrm{p}$ items is $\frac{(\mathrm{m}+\mathrm{n}+\mathrm{p}) \text { ! }}{\mathrm{m} ! \mathrm{n} ! \mathrm{p} !}$
- Number of ways to distribute $(\mathrm{m}+\mathrm{n}+\mathrm{p})$ items among 3 persons in the group containing $\mathrm{m}, \mathrm{n} \& \mathrm{p}$ items is $\frac{(\mathrm{m}+\mathrm{n}+\mathrm{p}) !}{\mathrm{m} ! \mathrm{n} ! \mathrm{p} !} 3$ !
(ii) Groups of equal size
- Number of ways in which $(\mathrm{mn})$ different items can be divided equally into $\mathrm{m}$ groups each containing n objects
$=\left\{\begin{array}{l}\frac{(m n) !}{(n !)^{m} m !} ; \text { if order of gorups is not impor tan } t \\ \frac{(m n) !}{(n !)^{m}} ; \text { if order of groups is impor tan } t\end{array}\right.$
Note
(i) If there are $m$ items of one kind, $n$ items of another kind, then the number of ways of choosing $\mathrm{r}$ items out of these $=$ coefficient of $\mathrm{x}^{\mathrm{r}}$ in $\left(1+\mathrm{x}+\mathrm{x}^{2}+\right.$.
(ii) If there are $m$ items of one kind $n$ items of another kind, then the number of ways of choosing $r$ items such that at least one item of each kind is included
$=$ coefficient of $\mathrm{x}^{\mathrm{r}}$ in $\left(\mathrm{x}+\mathrm{x}^{2}+\ldots . .+\mathrm{x}^{\mathrm{m}}\right)\left(\mathrm{x}+\mathrm{x}^{2}+\ldots .+\mathrm{x}^{\mathrm{n}}\right)$
8. Results related with points, Lines, Rectangle, Polygon, Circle, etc.
(i) If these are $n$ points in the plane, number of line segments ${ }^{n} \mathrm{C} _{2}$
(ii) Number of points $n$, then the number of triangles ${ }^{n} C _{3}$
(iii) Number of diagonals in a regular polygon having $\mathrm{n}$ sides $={ }^{n} \mathrm{C} _{2}-\mathrm{n}$
(iv) Number of parallelograms when a parallelogram is cut by two sets of $m$ lines parallel to its sides $={ }^{\mathrm{m}+2} \mathrm{C} _{2}{ }^{\mathrm{m}+2} \mathrm{C} _{2}$
(v) $\left\{\begin{array}{l}\text { Number of rectan gles }=\sum _{r=1}^{n} r^{3} \\ \text { Number of squares }=\sum _{r=1}^{n} r^{2}\end{array}\right.$
(vi) $\left\{\begin{array}{l}\text { Number of rec tan gles }={ }^{m+1} C _{2}{ }^{n+1} C _{2}=\frac{m n}{4}(m+1)(n+1) \\ \text { Number of squares }=\sum _{r=1}^{n}(m-r+1)(n-r+1)\end{array}\right.$
(vii) Maximum number of parts in which a plane can be divided by $\mathrm{n}$ straight lines $=1+\sum _{\mathrm{r}=1}^{\mathrm{n}} \mathrm{r}$
(viii) Maximum number of points of intersection of $n$ straight Lines $=1 \times{ }^{n} C _{2}$
(ix) Maximum number of points of intersection of $n$ circles $=2 \times{ }^{n} C _{2}$
(x) Maximum number of points of intersection of $n$ parabolas $=4 \times{ }^{n} C _{2}$
De-arrangement
Number of arrangement of $m$ things in a row so that none of them occupies its original place is $\mathrm{m} !\left\{1-\frac{1}{1 !}+\frac{1}{2 !}-\frac{1}{3 !}+\ldots \ldots .+(-1)^{\mathrm{m}} \frac{1}{\mathrm{~m} !}\right\}$
Exponent of prime $p$ in $n$ !
$E _{p}(n !)=\left[\frac{n}{p}\right]+\left[\frac{n}{p^{2}}\right]+\left[\frac{n}{p^{3}}\right]+\ldots \ldots \ldots .+\left[\frac{n}{p^{k}}\right]$ where $k$ is the largest positive integer such that $\mathrm{p}^{\mathrm{k}} \leq \mathrm{n}<\mathrm{p}^{\mathrm{k}+1}$
Solved examples
1. The number of zeroes at the end of 100 ! is
(a) 23
(b) 24
(c) 25
(d) None of these
Show Answer
Solution:
$\left[\frac{100}{5}\right]+\left[\frac{100}{5^{2}}\right]+\left[\frac{100}{5^{3}}\right]+………$
$=20+4+0$
$=24$
Answer: (b)
2. The total number of integral solutions of the triplet $(\mathrm{x}, \mathrm{y}, \mathrm{z})$ for the equation $\mathrm{xyz}=24$ is
(a) 30
(b) 60
(c) 120
(d) None of these
Show Answer
Solution:
$ \begin{aligned} 24.1 .1 \rightarrow \frac{3 !}{2 !} & =3 \\ 12.2 .1 \rightarrow 3 ! & =6 \\ 6.4 .1 \rightarrow 3 ! & =6 \\ 8.3 .1 \rightarrow 3 ! & =6 \\ 6.2 .2 \rightarrow \frac{3 !}{2 !} & =3 \\ 4.3.2 \rightarrow 3 ! & =6 \\ \therefore \text { Total } & =30 \end{aligned} $
30 positive integral solutions
Total number of integral solutions with negative integers included is $30 \times 4=120$
Answer: (c)
3. The total number of squares in a chess board is
(a) 64
(b) 65
(c) 204
(d) None of these
Show Answer
Solution:
$ 1^{2}+2^{2}+3^{2}+\ldots \ldots \ldots \ldots \ldots+8^{2}=\frac{8(8+1)(16+1)}{6}=204 $
Answer: (c)
4. $20$ lines pass through a given plane. The maximum number of parts in which the plane can be divided is
(a) 210
(b) 211
(c) 212
(d) None of these
Show Answer
Solution:
$ \begin{aligned} & \text { Use } 1+\sum \mathrm{n} \\ & =1+\sum 20=1+\frac{20.21}{2}=211 \end{aligned} $
Answer: (b)
5. The number of quadrilaterals that can be formed using 10 points in a plane out of which 4 are collinear is
(a) 210
(b) 209
(c) 185
(d) None of these
Show Answer
Solution:
$ { }^{10} \mathrm{C} _{4}-{ }^{4} \mathrm{C} _{4}-{ }^{4} \mathrm{C} _{3} \cdot{ }^{6} \mathrm{C} _{1}=185 $
Answer: (c)
6. The total number of distinct rational numbers $x$ such that $0<x<1$ and $x=\frac{p}{q}$ where $\mathrm{p}, \mathrm{q} \in\{1,2,3,4,5,6\}$ is
(a) 15
(b) 13
(c) 11
(d) None of these
Show Answer
Solution:
| Values of $\mathrm{p}$ | Possible rational numbers |
|---|---|
| 1 | $\frac{1}{2}, \frac{1}{3}, \frac{1}{4}, \frac{1}{5}, \frac{1}{6}$ |
| 2 | $\frac{2}{3}, \frac{2}{4}, \frac{2}{5}, \frac{2}{6}$ |
| 3 | $\frac{3}{4}, \frac{3}{5}, \frac{3}{6}$ |
| 4 | $\frac{4}{5}, \frac{4}{6}$ |
| 5 | $\frac{5}{6}$ |
Out of 15 possible rational numbers, only 11 are distinct.
Answer: (c)
7. The sum of 5 digit number in which only odd digits occur without repetition is
(a) 277775
(b) 555550
(c) 1111100
(d) None of these
Show Answer
Solution:
Sum of n digit numbers
$ \begin{aligned} & =(\text { Sum of digits }) \frac{\left(10^{\mathrm{n}}-1\right)}{10-1}(\mathrm{n}-1) ! \\ & =(1+3+5+7+9) \frac{\left(10^{5}-1\right)}{10-1}(5-1) ! \\ & =25 \times 11111 \times 24 \\ & =6666600 \end{aligned} $
Answer: (d)
Practice questions
1. An n digit number is a positive number with exactly $n$ digits. Nine hundred distinct n-digit numbers are to be formed using only the three digits 2,5 and 7. The smallest value of $\mathrm{n}$ for which this is possible is
(a) 6
(b) 7
(c) 8
(d) 9
Show Answer
Answer: (b)2. Match the following:
Consider all possible permutations of the letters of the word ENDEANOEL
| Column I | Column II |
|---|---|
| (a) The number of permutations containing the word ENDEA is | (p) $5 !$ |
| (b) The number of permutations in which the letteE occurs in the first and last position is | (q) $2 \times 5 !$ |
| (c) The number of permutations in which none of the lette $\mathrm{D}, \mathrm{L}, \mathrm{N}$ occurs in the last five positions is | (r) $7 \times 5 !$ |
| (d) The number of permutations in which the letter $A, E, O$ occur only in odd positions is | (S) $21 \times 5 !$ |
Show Answer
Answer: a$\rarr$ p; b $\rarr$ s; c $\rarr$ q; d $\rarr$ q3. Five balls of different colors are to be placed in 3 boxes of different sizes. Each box can hold all 5 balls. The number of ways we can place the balls so that no box is empty, is
(a) 116
(b) 126
(c) 144
(d) 150
Show Answer
Answer: (d)4. A student is allowed to select atmost $n$ books from a collection of $(2 n+1)$ books. If number of ways in which he can select atleast one book is 63 , then $\mathrm{n}=$
(a) 3
(b) 4
(c) 6
(d) 5
Show Answer
Answer: (a)5. A rectangle with sides $2 \mathrm{~m}-1,2 \mathrm{n}-1$ is divided into squares of unit length by drawing lines parallel to sides of a rectangle. The number of rectangles with odd side length is
(a) $(\mathrm{m}+\mathrm{n}+1)^{2}$
(b) $\mathrm{mn}(\mathrm{m}+1)(\mathrm{n}+1)$
(c) $m^{2} n^{2}$
(d) $4^{\mathrm{m}+\mathrm{n}-1}$
Show Answer
Answer: (c)6. Out of 5 apples, 10 mangoes and 15 oranges, the number of ways of distributing 15 fruits each to two persons, is
(a) 56
(b) 64
(c) 66
(d) 72
Show Answer
Answer: (c)7. Match the following
| Column I | Column II |
|---|---|
| (a). The number of positive integral solutions of the equati $\mathrm{x} _{1} \mathrm{x} _{2} \mathrm{X} _{3} \mathrm{x} _{4} \mathrm{x} _{5}=1050$ is $\lambda$, then $\lambda$ is divisible by | (p). 3 |
| (b). Let be the element of the set $\mathrm{A}=\{1,2,3,5,6,10,15,30\}$ an$x _{1}, x _{2}, x _{3}$ be integers such that $x _{1} x _{2} x _{3}=y$.If $\lambda$ be the numbeof integral solutions of $\mathrm{x} _{1} \mathrm{x} _{2} \mathrm{x} _{3}=\mathrm{y}$, then $\lambda$ is divisible by | (q). 4 |
| (c). Let a be a factor of 120 . If $\lambda$ be the number of positive integral solutions o$\mathrm{x} _{1} \mathrm{x} _{2} \mathrm{x} _{3}=\mathrm{a}$, then $\lambda$ is divisible by | (r). 5 |
| (s). 8 | |
| (t). 16 |
Show Answer
Answer: a $\rarr$ p, r; b $\rarr$ q, s, t; c $\rarr$ q, s, r, t8. The maximum number of points into which 4 circles & 4 straight lines intersect is
(a) 26
(b) 50
(c) 56
(d) 72
Show Answer
Answer: (b)9. A is a set containing $\mathrm{n}$ elements. A subset $\mathrm{P} _{1}$ is chosen and $\mathrm{A}$ is reconstructed by replacing the elements of $\mathrm{P} _{1}$. The same process is repeated for subsets $\mathrm{P} _{2}, \ldots \ldots . \mathrm{P} _{\mathrm{m}}$ with $\mathrm{m}>1$. The number of ways of choosing $\mathrm{P} _{1}, \mathrm{P} _{2}, \ldots \ldots ., \mathrm{P} _{\mathrm{m}}$, so that $\mathrm{P} _{1} \cup \mathrm{P} _{2} \cup \ldots \ldots \cup \mathrm{P} _{\mathrm{m}}=\mathrm{A}$ is
(a) $\left(2^{\mathrm{m}}-1\right)^{\mathrm{mn}}$
(b) $\left(2^{\mathrm{n}}-1\right)^{\mathrm{m}}$
(c) ${ }^{m+n} C _{m}$
(d) None of these
Show Answer
Answer: (d)10. Number of points having position vector $a \hat{i}+b \hat{j}+c \hat{k}$ where $a, b, c \in\{1,2,3,4,5$,$\}$ such that $2^{a}+3^{b}+5^{c}$ is divisible by 4 is
(a) 70
(b) 140
(c) 210
(d) 280
Show Answer
Answer: (a)11. Read the passage and answer the following questions.
$\mathrm{A}$ is a set containing $\mathrm{n}$ elements. $\mathrm{A}$ subset $\mathrm{P}$ of $\mathrm{A}$ is chosen and the set $\mathrm{A}$ is reconstructed by replacing the elements of P. A subset Q of A is chosen again. Find the number of ways of choosing P & Q when
(i) $\mathrm{Q}$ is subset of $\mathrm{P}$ is
(a) $3^{\mathrm{n}}$
(b) $2^{\mathrm{n}}$
(c) $n.3 \mathrm{n}^{-1}$
(d) None of these
Show Answer
Answer: (a)(ii) $\mathrm{P} \& \mathrm{Q}$ contain just one element is
(a) $2^{\mathrm{n}}$
(b) $3^{\mathrm{n}}$
(c) $n \cdot 3^{n-1}$
(d) None of these
Show Answer
Answer: (c)(iii) $\mathrm{P}=\mathrm{Q}$ is
(a) $2^n$
(b) $3^n$
(c) $n .3^{n-1}$
(d) None of these
