Fundamental principle of counting

(i) Addition principle : If an operation can be performed in ’ $m$ ’ different ways and another operation which is independent of the first operation, can be performed in ’ $n$ ’ different ways then either of then can be performed in $(m+n)$ ways.

(ii) Multiplication Principle. If an operation can be performed is ’ $m$ ’ different ways; following which a second operation can be performed in ’ $n$ ’ different ways, then the two operations in succession can be performed in ’ $\mathrm{mn}$ ’ ways.

Permutation

Number of permutations of $n$ distinct things taking $r(1 \leq r \leq n)$ at a time is denoted by ${ }^{n} P _{r}$.

${ }^{n} P _{r}=\dfrac{n !}{(n-r) !}$

• Number of ways of filling $r$ places using $n$ things if repetition is allowed $=n^{r}$

Circular Permutation

Number of circular permutations of $n$ things $=(n-1)$ !

Number of circular permutations of $n$ different things taken $r$ at a time $=\dfrac{{ }^{n} P _{r}}{r}$

Number of circular permutations of $n$ different things when clockwise and anticlockwise circular permutations are considered as same is $\dfrac{(\mathrm{n}-1) !}{2}$

Note : When position are marked, circular arrangement is assumed to be linear.

Combination

Number of combinations of $n$ distinct things taking $r$ at a time is denoted by ${ }^{n} C _{r}$.

${ }^{\mathrm{n}} \mathrm{C} _{\mathrm{r}}=\dfrac{\mathrm{n} !}{\mathrm{r} !(\mathrm{n}-\mathrm{r}) !}$

Note: ${ }^{n} \mathrm{P} _{\mathrm{r}}=\mathrm{r}$ ! ( $\left.{ }^{\mathrm{n}} \mathrm{C} _{\mathrm{r}}\right)$

Note the following facts

(i) ${ }^{n} C _{0}={ }^{n} C _{n}=1$

(ii) ${ }^{n} \mathrm{C} _{\mathrm{r}}={ }^{n} \mathrm{C} _{\mathrm{n}-\mathrm{r}} \quad(0 \leq \mathrm{r} \leq \mathrm{n})$

(iii) ${ }^{n} \mathrm{C} _{\mathrm{r}-1}+{ }^{\mathrm{n}} \mathrm{C} _{\mathrm{r}}={ }^{\mathrm{n}+1} \mathrm{C} _{\mathrm{r}} \quad(1 \leq \mathrm{r} \leq \mathrm{n})$

(iv) ${ }^{n} C _{r}={ }^{n} C _{s} \Rightarrow\left\{\begin{array}{l}r=s \\ \text { or } r+s=n\end{array}\right.$

(v) Greatest value of ${ }^{n} C _{r}=\left\{\begin{array}{l}{ }^{n} C _{\dfrac{n}{2}} \text { if } n \text { is even } \\ { }^{n} C _{\dfrac{n-1}{2}} \text { or }{ }^{n} C _{\dfrac{n+1}{2}} \text { if } n \text { is odd }\end{array}\right.$

Important Results

1. Total number of selections of one or more objects from $\mathrm{n}$ different objects

$={ }^{n} C _{1}+{ }^{n} C _{2}+\ldots .+{ }^{n} C _{n}=2^{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}(p+1)(q+1) 2^{r}-1 \text { (if at least one thing to be selected) } \\ (p+1)(q+1) 2^{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+r-1} \mathrm{C} _{\mathrm{r}-1}$

6. Results on distribution

Distribution of $n$ things to $r$ boxes

7. Division of items into groups

(i) Groups of unequal size.

• $\quad$ Number of ways in which $(m+n+p)$ items can be divided into unequal groups containing $\mathrm{m}, \mathrm{n}$, p items is $\dfrac{(\mathrm{m}+\mathrm{n}+\mathrm{p}) \text { ! }}{\mathrm{m} ! \mathrm{n} ! \mathrm{p} !}$
• $\quad$ Number of ways to distribute $(m+n+p)$ items among 3 persons in the group containing $\mathrm{m}, \mathrm{n}$ & $\mathrm{p}$ items is $\dfrac{(\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}\dfrac{(m n) !}{(n !)^{m} m !} ; \text { if order of gorups is not impor tan } t \\ \dfrac{(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 $r$ items out of these $=$ coefficient of $x^{r}$ in $\left(1+x+x^{2}+\right.$ $\left.+x^{m}\right)\left(1+x+x^{2}+\ldots \ldots .+x^{n}\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 rectangles }=\sum\limits _{r=1}^{n} r^{3} \\ \text { Number of squares }=\sum\limits _{r=1}^{n} r^{2}\end{array}\right.$

(vi) $\left\{\begin{array}{l}\text { Number of rectangles }={ }^{m+1} C _{2}{ }^{n+1} C _{2}=\dfrac{m n}{4}(m+1)(n+1) \\ \text { Number of squares }=\sum\limits _{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\limits _{\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-\dfrac{1}{1 !}+\dfrac{1}{2 !}-\dfrac{1}{3 !}+\ldots \ldots .+(-1)^{\mathrm{m}} \dfrac{1}{\mathrm{~m} !}\right\}$

Exponent of prime $\mathbf{p}$ in $\mathbf{n}$ !

$E _{p}(n !)=\left[\dfrac{n}{p}\right]+\left[\dfrac{n}{p^{2}}\right]+\left[\dfrac{n}{p^{3}}\right]+\ldots \ldots \ldots+\left[\dfrac{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

2. The total number of integral solutions of the triplet $(x, y, z)$ for the equation $x y z=24$ is

(a) 30

(b) 60

(c) 120

(d) None of these

3. The total number of squares in a chess board is

(a) 64

(b) 65

(c) 204

(d) None of these

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

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

6. The total number of distinct rational numbers $x$ such that $0<x<1$ and $x=\dfrac{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

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

Exercise

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 $n$ for which this is possible is

(a) 6

(b) 7

(c) 8

(d) 9

2. Match the following:

Consider all possible permutations of the letters of the word ENDEANOEL

3. 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

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

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) $\mathrm{m}^{2} \mathrm{n}^{2}$

(d) $4^{\mathrm{m}+\mathrm{n}-1}$

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

7. Match the following

8. The maximum number of points into which 4 circles & 4 straight lines intersect is

(a) 26

(b) 50

(c) 56

(d) 72

9. A is a set containing $n$ elements. A subset $P _{1}$ is chosen and $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) ${ }^{\mathrm{m}+\mathrm{n}} \mathrm{C} _{\mathrm{m}}$

(d) None of these

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

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^{\text {n }}$

(b) $2^{\mathrm{n}}$

(c) n.3 $\mathrm{n}^{-1}$

(d) None of these

(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

(iii) $\mathrm{P}=\mathrm{Q}$ is

(a) $2^{\mathrm{n}}$

(b) $3^{\mathrm{n}}$

(c) $n .3^{n-1}$

(d) None of these