Permutation And Combination
Arrangement:
$\quad$ Number of permutations of $n$ different things taken $r$ at a time $=$
$${ }^{n} P_{r}=n(n-1)(n-2) \ldots(n-r+1)=\frac{n !}{(n-r) !}$$
Circular permutation :
$\quad$ The number of circular permutations of $n$ different things taken all at a time is; $(n-1)$ !
Selection :
$\quad$ Number of combinations of $n$ different things taken $r$ at a time
$$={ }^{n} C_{r}=\frac{n !}{r !(n-r) !}=\frac{{ }^{n} P_{r}}{r !}$$
$\quad$ 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 another type,
$\quad$ ’ $r$ ’ of them are similar & of a third type & the remaining $n-(p+q+r)$ are all different is
$$\frac{n !}{p ! q ! r !}$$
Selection of one or more objects:
- Number of ways in which atleast one object be selected out of ’ $n$ ’ distinct objects is
$$ { }^{n} C_{1}+{ }^{n} C_{2}+{ }^{n} C_{3}+\ldots \ldots \ldots \ldots \ldots+{ }^{n} C_{n}=2^{n}-1 $$
- Number of ways in which atleast one object may be selected out of ’ $p$ ’ alike objects of one type ’ $q$ ’ alike objects of second type and ’ $r$ ’ alike of third type is
$$ (p+1)(q+1)(r+1)-1 $$
- Number of ways in which atleast one object may be selected from ’ $n$ ’ objects where ’ $p$ ’ alike of one type ’ $q$ ’ alike of second type and ’ $r$ ’ alike of third type and rest $n-(p+q+r)$ are different is
$$(p+1)(q+1)(r+1) 2^{n-(p+q+r)}-1 $$
Multinomial theorem :
$\quad$ Coefficient of $X^{r}$ in expansion of
$$(1-x)^{-n}={ }^{n+r-1} C_{r}(n \in N)$$
$\quad$ Let $N=p^{a} q^{b} r^{c} \ldots .$. where $p, q, r \ldots \ldots$ are distinct primes & $a, b, c \ldots .$. are natural numbers then :
-
The total numbers of divisors of $\mathrm{N}$ including 1 & N is $=(\mathrm{a}+1)(\mathrm{b}+1)(\mathrm{c}+1) \ldots \ldots \ldots$
-
The sum of these divisors is $=$
$$ \left(p^{0}+p^{1}+p^{2}+\ldots .+p^{a}\right)\left(q^{0}+q^{1}+q^{2}+\ldots .+q^{b}\right) \left(r^{0}+r^{1}+r^{2}+\ldots .+r^{c}\right) \ldots \ldots $$
-
Number of ways in which $\mathrm{N}$ can be resolved as a product of two factors is
-
$$ =\frac{1}{2}(a+1)(b+1)(c+1) \ldots . \hspace{2mm} \text { if N is not a perfect square.} $$
-
$$ =\frac{1}{2}[(a+1)(b+1)(c+1) \ldots+1] \hspace{2mm} \text { if N is a perfect square.}$$
-
-
Number of ways in which a composite number $\mathrm{N}$ can be resolved into two factors which are relatively prime (or coprime) to each other is equal to $2^{n-1}$ where $\mathrm{n}$ is the number of different prime factors in $\mathrm{N}$.
Dearrangement :
$\quad$ Number of ways in which ’ $n$ ’ letters can be put in ’ $n$ ’ corresponding envelopes such that no letter goes to correct envelope is $$n !\left(1-\frac{1}{1 !}+\frac{1}{2 !}-\frac{1}{3 !}+\frac{1}{4 !} \ldots \ldots \ldots .+(-1)^{n} \frac{1}{n !}\right)$$
Principle of counting :
PYQ-2023-P&C-Q9, PYQ-2023-P&C-Q12, PYQ-2023-P&C-Q15, PYQ-2023-P&C-Q20
-
The rule of sum: If a first task can be performed in m ways, while a second task can be performed in n ways, and the tasks cannot be performed simultaneously, then performing either one of these tasks can be accomplished in any one of total m+n ways.
-
The rule of product: If a procedure can be broken down into first and second stages, and if there are m possible outcomes for the first stage and if, for each of these outcomes, there are n possible outcomes for the second stage, then the total procedure can be carried out, in the designated order, in a total of mn ways.
Factorial notation:
$$n! = n(n-1)…(3)(2)(1)$$
Permutation:
PYQ-2023-P&C-Q1 , PYQ-2023-P&C-Q8, PYQ-2023-P&C-Q16, PYQ-2023-P&C-Q20
The number of permutations of n different objects taken r at a time is represented as $$ ^n P_r = \frac{n!}{(n-r)!}$$
- Permutation with repetition: PYQ-2023-P&C-Q12
The no. of permutations of n different objects taken r at a time when each object may be repeated any number of times is $$n^r$$
-
Permutation of alike objects: The number of permutations of n objects taken all at a time in which, p are alike objects of one kind, q are alike objects of second kind & r are alike objects of a third kind and the rest (n - (p + q + r)) are all different is $$\frac{n!}{p! q! r!}$$
-
Permutation with Restriction: PYQ-2023-P&C-Q7 PYQ-2023-P&C-Q18
The number of permutations of n different objects, taken all at a time, when m specified objects always come together is $$m! × (n - m + 1)!$$
- Non-consecutive selection: PYQ-2023-P&C-Q10 PYQ-2023-P&C-Q11 PYQ-2023-P&C-Q14
$\quad \quad$• The number of selections of r consecutive objects out of n objects in a row $$= n - r + 1$$
$\quad \quad$• The number of selections of r consecutive objects out of n objects along a circle $$= n , \text{~ when~} r<n$$ $$= 1 , \text{~ when~} r=n$$
Circular permutation:
The number of circular arrangements of n different objects $$= (n - 1)!$$
-
Clockwise and anticlockwise arrangements:
-
When clockwise and anticlockwise arrangements are not different, i.e. when observations can be made from both sides, the number of circular arrangements of n different objects is $$\frac{(n - 1)!}{2}$$
-
The number of circular permutation of n different objects taken all at a time is (n - 1)!, if clockwise and anticlockwise orders are taken as different.
-
The number of circular permutations of n different objects taken r at a time
-
$\frac{^nP_r}{r}$, when clockwise and anticlockwise orders are treated as different.
-
$\frac{^nP_r}{2r}$, when clockwise and anticlockwise orders are treated as same.
-
-
Properties of permutation:
-
${ }^n P_n=n(n-1)(n-2) \ldots 3 \times 2 \times 1=n$!
-
${ }^n P_0=\frac{n !}{n !}=1$
-
${ }^n P_1=n$
-
${ }^n P_{n-1}=n$ !
-
${ }^n P_r=n \cdot{ }^{n-1} P_{r-1}=n(n-1)^{n-2} P_{r-2}$
-
${ }^{n-1} P_r+r \cdot{ }^{n-1} P_{r-1}={ }^n P_r$
-
$\frac{{ }^n P_r}{{ }^n P_{r-1}}=n-r+1$
Combination:
$\quad$ The number of all combinations of n objects, taken r at a time is generally denoted by C(n, r) or $^nC_r$ is $$ ^n C_r = \frac{n!}{r! (n-r)!}$$
-
Properties:
-
${ }^n C_r={ }^n C_{n-r}$
-
${ }^n C_r+{ }^n C_{r-1}={ }^{n+1} C_r$
-
${ }^n C_x={ }^n C_y \Rightarrow x=y$ or $x+y=n$
-
If $n$ is even, then the greatest value of ${ }^n C_r$ is ${ }^n C_{n / 2}$
-
If $n$ is odd, then the greatest value of ${ }^n C_r$ is ${ }^n C_{\frac{n+1}{2}}$
-
${ }^n C_0+{ }^n C_r+$ .. $+{ }^n C_n=2^n$
-
${ }^n C_n+{ }^{n+1} C_n+{ }^{n+2} C_n+$ $+{ }^{2 n-1} C_n={ }^{2 n} C_{n+1}$
-
Combinations under restrictions:
PYQ-2023-P&C-Q2, PYQ-2023-P&C-Q13, PYQ-2023-Matrices-Q13
-
Number of ways of choosing r objects out of n different objects if p particular objects must be excluded the required number of ways $$= ^{n-p}C_r$$
-
Number of ways of choosing r objects out of n different objects if p particular objects must be included (p ≤ r). the required number of ways $$= ^{n-p}C_{r-p}$$
-
The total number of combinations of n different objects taken one or more at a time $$= 2^n - 1$$
Combinations of alike objects:
PYQ-2023-P&C-Q5, PYQ-2023-P&C-Q6
$\quad$ If out of (p + q + r + s) objects, p are alike of one kind, q are alike of a second kind, r are alike of the third kind and s are different, then the total number of combinations is $$(p + 1)(q + 1)(r + 1)2^s - 1$$
Division into groups:
-
The number of ways in which (m + n) different objects can be divided into two unequal groups containing m and n objects respectively is $$\frac{(m+n)!}{m! n!}$$
-
If m = n, the groups are equal and in this case the number of division is $\frac{(2n)!}{n!n!2!} $; as it is possible to interchange the two groups without obtaining a new distribution.
-
The number of ways in which mn different objects can be divided equally into m groups if order of groups is not important is $$\frac{m n!}{(n!)^m m!}$$
-
The number of ways in which mn different objects can be divided equally into m groups if the order of groups is important is $$\frac{(m n)!}{(n!)^m }$$
