Permutations

Permutations

Fundamental Principles of Counting

A. Multiplication Principle

If first operation can be performed in $m$ ways and then second operation can be performed in $n$ ways. Then, the two operations taken together can be performed in $mn$ ways. This can be extended to any finite number of operations.

B. Addition Principle

If an operation can be performed in $m$ ways and another operation, which is independent of the first, can be performed in $n$ ways . Then, either of the two operations can be performed in $m+n$ ways, This can be extended to any finite number of mutually exclusive events.

Factorial

For any natural number $n$ , we define factorial as

$n!$ =$n\left(n-1\right)\left(n-2\right).......3\times 2\times 1.$

Properties of Factorial Notation

(i)$0!=1!=1$

(ii) Factorials of negative integers and fractions are no defined.

(iii) $n!=n\left(n-1\right)!=n\left(n-1\right)\left(n-2\right)!$

(iv) $\frac{n!}{r!}=n\left(n-1\right)\left(n-2\right)........\left(r+1\right)$

Exponent of Prime $p$ in $n$!

Let $n$ a positive integer and $p$ be a prime number.

Then, least integer amongst 1,2,3…….$\left(n-1\right),n$ which is divisible by $p$ is $\left[\frac{n}{p}\right]p,$ where $\left[\frac{n}{p}\right]$ denotes the greastest integer less than or equal to $\left[\frac{n}{p}\right].$

Permutation

Each of the different arrangement whicvh can be made by taking some or all of a number of things is called a permutation.

Mathematically the number of ways fo arranging $n$ distinct objects in a row takign $r\left(0<r\le n\right)$ at a time is denoted by $p\left(n,r\right)$ or ${}^n{p}_{r\cdot }$

i.e. ${}^n{p}_r=\frac{n!}{\left(n-r\right)!}$

Properties of Permutation

1 ${}^n{p}_n=n\left(n-1\right)\left(n-2\right)......1=n!$

2 ${}^n{p}_0=\frac{n!}{n!}=1$

3 ${}^n{p}_1=n$

4 ${}^n{p}_{n-1}=n!$

5 ${}^n{p}_r=n.{}^{n-1}{p}_{r-1}=n\left(n-1\right).{}^{n-2}{p}_{r-2}=n\left(n-1\right)\left(n-2\right).{}^{n-3}{p}_{r-3}$

6 ${}^{n-1}{p}_r+r.{}^{n-1}{p}_{r-1}={}^n{p}_r$

7 $\frac{{}^n{p}_n}{{}^n{p}_{r-1}}=n-r+1$

Important Results on Permutation

1. The number of permutations of $n$ different things taken $r$ at a time, when e ach thing may be repeated any number of times is $n^{r.}$

2. The number of permutations of $n$ different things taken all at a time is ${}^n{p}_n=n!$

3. The number of permutations of $n$ things taken all at a time, in which $p$ are a like of one kind, $q$ are alike of second kind and $r$ are alike of third kind and rest are different is

$\frac{n!}{p!q!r!}.$

4. The number of permutations of $n$ things of which $p_1$ are alike of one kind, $p_2$ are alike of second kind, $p_3$ are alike of third kind, …….,$p_r$ are alike of rth kind such that $p_{1+}{p}_2+p_3+........+p_r=n$ is

$\frac{n!}{p_1!p_2!p_3!.....p_r!}$

5. Number of permutations of $n$ different things taken $r$ at a time,

(a). When a particular things is be included in each arrangement

$r{.}^{n-1}{p}_{r-1}.$

(b). When a particular things is always excluded, then number of arrangements ${=}^{n-1}{p}_r.$

8. Number of permutations $n$different things taken all at a time, when $m$ specified things always come together is

$m!\left(n-m+1\right)!.$

9. Number of permutations of $n$ different things taken all at a time, when $m$ specified things never come together is

$n!-m!\times \left(n-m+1\right)!.$

10. Number of permutations of $n$ different things, taken $r$ at a times when $p$ particular things are to be always included in each arrangement is $p!{\left\{r-\left(p-1\right)\right\}}^{n-p}{p}_{r-p}.$

Division into Group

1. The number of ways in which $\left(m+n\right)$ different things can be divided into two group which contain $m$ and $n$ things respectively

$=\frac{\left(m+n\right)!}{m!n!}.$

This can be extended to $\left(m+n+p\right)$ different things divided into three groups of $m,n,p$ things respectively $=\frac{\left(m+n+p\right)!}{m!n!p!}.$

2. The number of ways of dividing $2n$ different elements into two groups of $n$ objects each is $\frac{\left(2n\right)!}{{\left(n!\right)}^2},$ when the distinction can be made between the groups, i.e. if the order of group is important .

This can be extended to $3n$ different elements into 3 groups is $\frac{\left(3n\right)!}{\left(n!\right)}.$

3. The number of was of dividing $2n$ different elements into two groups of $n$ object when no distinction can be made between the groups is not important is

$\frac{\left(2n\right)!}{2!{\left(n!\right)}^2}.$ This can be extended to $3n$ different elements into 3 groups is $\frac{\left(3n\right)!}{3!{\left(n!\right)}^3}.$

4. The number of ways in which $mn$ different things can be divided equally it into $m$ groups each containing $n$ objects, if order of the if order of the group is not important is

$\frac{\left(mn\right)!}{{\left(n!\right)}^{m}m!}.$

5. If the order of the group is important, then number of ways of dividing $mn$ different things equally into $m$ distinct groups each containing $n$ objects is

$\frac{\left(mn\right)!}{{\left(n!\right)}^m}.$

6. The number of ways of dividing $n$ identical things among $r$ groups taking into account the order to the groups and also the order to thing in each groups is

${}^{n+r-1}{p}_n=r\left(r+1\right)\left(r+2\right).....\left(r+n-1\right).$

7. The number of ways of dividing $n$ identical things among $r$ persons such that each gets $1,2,3,.....ork$ things is the coefficient of $x^{n-r}$ in the expansion of ${\left(1+x+x^2+.....+x^{k-1}\right)}^r.$

Circular Permutation

In a circular permutation, firstly we fix the position for one of the objects and then arrange the other objects in all possible ways.

1 Number of circular permutation of $n$ different things taken all at a time is $\left(n-1\right)!.$ If clockwise and anti-clockwise orders are different.

2 Number of circular permutations of $n$ different things taken all at a time, when clockwise order is not different $=\frac{1}{2}\left(n-1\right)!.$

3 Number of circular permutations of $n$different things taken $r$ at a time , when clockwise or anti-clockwise orders are take as different is $\frac{{}^n{p}_r}{r}.$

4 Number of circular permutations of $n$ different things taken $r$at is a time , when clockwise or anti-clockwise orders are not different is $\frac{{}^n{p}_{r.}}{2r}$.

5 If we mark numbers 1to $n$ on chairs in a round table, then $n$ persons sitting around table is $n!.$