Fundametal 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 them can be performed in $(m+n)$ ways.

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

Factorial

The continued product of first $n$ natural numbers is $n !$.

$\mathrm{n} !=1.2 .3$ n

value of 0 ! is 1

Exponent of prime $p$ is $n$ !

Let $n$ be a positive integer and $p$, a prime number. Then the exponent of $p$ is $n$ ! is given by $\mathrm{E} _{\mathrm{p}}(\mathrm{n} !)=\left[\frac{\mathrm{n}}{\mathrm{p}}\right]+\left[\frac{\mathrm{n}}{\mathrm{p}^{2}}\right]+\left[\frac{\mathrm{n}}{\mathrm{p}^{3}}\right]+\ldots \ldots \ldots+\left[\frac{\mathrm{n}}{\mathrm{p}^{\mathrm{s}}}\right]$ where $\mathrm{s}$ in the largest positive integer such that $\mathrm{p}^{\mathrm{s}}<\mathrm{n}<\mathrm{p}^{\mathrm{s}+1}$

Permutation

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

$ { }^{n} P _{r}=\frac{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 $=\frac{{ }^{n} P _{r}}{r}$

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

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

Combination

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

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

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

Properties of ${ }^{n} P _{r}$ and ${ }^{n} C _{r}$

i. ${ }^{n} P _{n}=n ! ;{ }^{n} C _{o}={ }^{n} C _{n}=1$

ii. ${ }^{n} P _{r}={ }^{n-1} P _{r-1}+r{ }^{n-1} P _{r-1}$

iii. $\quad \sum _{\mathrm{r}=1}^{\mathrm{n}} \mathrm{r} \cdot{ }^{\mathrm{r}} \mathrm{P} _{\mathrm{r}}={ }^{\mathrm{n}+1} \mathrm{P} _{\mathrm{n}+1}-1$

iv. ${ }^{\mathrm{n}} \mathrm{C} _{\mathrm{r}}={ }^{\mathrm{n}} \mathrm{C} _{\mathrm{s}} \Rightarrow$ either $\mathrm{r}=\mathrm{s}$ or $\mathrm{r}+\mathrm{s}=\mathrm{n}$

v. ${ }^{n} C _{r}$ is greatest, $\left\{\begin{array}{l}r=\frac{n}{2} ; \text { if } n \text { is even } \\ r=\frac{n \pm 1}{2} ; \text { if } n \text { is od(d). }\end{array}\right.$

vi. ${ }^{n} C _{r}={ }^{n} C _{n-r}=\frac{n}{r}{ }^{n-1} C _{r-1}$

vii. $\frac{{ }^{\mathrm{n}} \mathrm{C} _{\mathrm{r}}}{{ }^{\mathrm{n}} \mathrm{C} _{\mathrm{r}-1}}=\frac{\mathrm{n}-\mathrm{r}+1}{\mathrm{r}}$

viii. ${ }^{n} C _{r-1}+{ }^{n} C _{r}={ }^{n+1} C _{r}$

Solved examples

1. How many 5-digit numbers divisible by 3 can be formed using digits $0,2,4,6,8$, 9, if repetition not allowed?

2. How many 5 -digit numbers divisible by 4 can be formed using digits $0,2,4,7,8,9$, if repetition not allowed?

3. How many 5 -digit numbers divisible by 6 can be formed using digits $0,2,4,5,6,8$, if repetition not allowed.

4. The total number of odd natural numbers that can be formed with the digits $1,3,1,5,4,1,4$ and are greater than 2 million are

(a) 120

(b) 160

(c) 180

(d) none

5. The total number of 4 digit numbers greater than 4000 , whose sum of digits is odd is

(a). $2800$

(b). $3000$

(c). $ 3600$

(d). none of these

6. Mohan writes a letter to five of his friends and addresses them. The number of ways in which the letters can be placed in the envelopes so that that three of them are in the wrong envelopes is

(a). 44

(b). 119

(c). 21

(d). 20

7. In how many ways the squares of the figure given below be filled up with letters of the word ‘ROHINI’, so that each row contains atleast one letter.

Practice questions

1. Number of polynomials of the form $\mathrm{x}^{3}+\mathrm{ax}^{2}+\mathrm{bx}+\mathrm{c}$ that are divisible by $\mathrm{x}^{2}+1$, where $\mathrm{a}, \mathrm{b}, \mathrm{c} \varepsilon\{1$, $2,3, \ldots . .9,10\}$

(a). 30

(b). 1000

(c). 10

(d). none of these

2. The number of ways in which we can select four numbers from 1 to 30 so as to exclude every selection of four consecutive number is

(a). 27378

(b). 27405

(c). 27399

(d). none of these

3. The number of ordered pairs of integers $(x, y)$ satisfying the equation $x^{2}+6 x+y^{2}=4$ is

(a). 2

(b). 8

(c). 6

(d). none of these

4. How many six digit numbers are there in which sum of the digits is divisible by 5

(a). $18,0000$

(b). $54,0000$

(c). $5 \times 10^{5}$

(d). none of these

5. Ten IIT and 2 DCE students sit in a row. The number of ways in which exactly 3 IIT students sit between 2 DCE students is

(a). ${ }^{10} \mathrm{C} _{3} \times 2 ! \times 3 ! \times 8$ !

(b). $10 ! 2 ! 3 ! \times 8$ !

(c). $5 ! \times 2 ! \times 9 ! \times 8$ !

(d). none of these

6. Let there are $n \geq 3$ circles. The value of $n$ for which the number of radical centres is equal to the number of radical axis is (assume that all radical axis and radical centres exist and are different)

(a). 7

(b). 6

(c). 5

(d). none of these

7. Total number of integers ’ $n$ ’ such that $2 \leq n \leq 2000$ and HCF of $n$ and 36 is one, is equal to

(a). 666

(b). 667

(c). 665

(d). none of these

8. Match the following:-

9. The number of ordered triplets $(a, b, c)$ such that $\operatorname{LCM}(a, b)=1000, \operatorname{LCM}(b, c) 2000$ and $\operatorname{LCM}(\mathrm{c}, \mathrm{a})=2000$ is $………..$

10. Read the paragraph and answer the questions that follow :-

Number of ways of distributing $n$ different things into $r$ different groups is $r^{\mathrm{n}}$ when blank groups are taken into account and is $\mathrm{r}^{\mathrm{n}}-{ }^{\mathrm{r}} \mathrm{C} _{1}(\mathrm{r}-1)^{\mathrm{n}}+{ }^{\mathrm{r}} \mathrm{C} _{2}(\mathrm{r}-2)^{2} \ldots \ldots \ldots .+(-1)^{\mathrm{r}-1 \mathrm{r}} \mathrm{C} _{\mathrm{r}-1}$ when blank groups are permitte(d).

i. 4 candidates are competing for two managerial posts. In how many ways can the candidates be selected?

(a). $4^{2}$

(b). ${ }^{4} \mathrm{C} _{2}$

(c). $2^{4}$

(d). none of these

ii. 8 different balls can be distributed among 3 children so that every child receives at least one ball is

(a). $3^{8}$

(b). ${ }^{8} \mathrm{C} _{3}$

(c). $8^{3}$

(d). none of these

iii. 5 letters can be posted into 3 letter boxes in

(a). $3^{5}$ ways

(b). $5^{3}$ ways

(c). ${ }^{5} \mathrm{C} _{3}$ ways

(d). none of these