Permutation and Combination

# Combination

In permutation, we arrange a set of objects in some order. But combination of a set of objects means just their collection without any regard to order or arrangement.

There is only one combination of $n$ objects; but for the same $n$ objects, the number of permutations is $n!$. Similarly, the number of combinations of $n$ objects taken $r$ at a time is less than the number of permutations of $n$ objects taken $r$ at a time.

The combination of $n$ objects taken $r$ at a time is denoted by $C(n,r)$ or $^nC_r$.

## Theorem: The total number of combinations of $n$ objects taken $r$ at a time is given by $C(n,r)=\frac{n!}{(n-r)!\,r!}$

Proof: Consider any one of the $C(n,r)$ combinations. This combination contains $r$ objects, these $r$ objects can be arranged among themselves in $r!$ different ways. So, for each combination, there are $r!$ permutations.

Consequently for the $C(n,r)$ possible combinations, there are $C(n,r)\cdot r!$ different permutations. Since these are all possible permutations of $n$ objects taken $r$ at a time, we have, $C(n,r)\cdot r!=P(n,r)=\frac{n!}{(n-r)!}$ $\therefore C(n,r)=\frac{n!}{(n-r)!\,r!}$

### Cor.1 Complementary Combination:

The number of combinations of $n$ objects taken $r$ at a time is equal to the number of combinations of $n$ objects taken $n-r$ at a time $\text{i.e.}\;\;\; C(n,r)=C(n,n-r)$

Proof: We have, $\begin{array}{l} & C(n,n-r) &= \frac{n!}{(n-n+r)!\,(n-r)!} \\ & & = \frac{n!}{r!\,(n-r)!} \\ & &= C(n,r) \\ \therefore & C(n,r) &= C(n,n-r) \end{array}$

Cor.2: If $C(n,r)=C(n,r’)$, then either $r=r’$ or $r+r’=n$.

$\begin{array}{l} \text{Given,} & C(n,r) &= C(n,r’) \\ \text{or,} & C(n,r) &= C(n,n-r’) \\ \Rightarrow & r &= n-r’ \\ \therefore & r+r’ &= n \\ \text{Also,} & C(n,r) &= C(n,r’) \\ \Rightarrow & r &= r’ \end{array}$ $\therefore$ If $C(n,r)=C(n,r’)$, then either $r=r’$ or $r+r’=n$.

Cor.3: $C(n,r)+C(n,r-1)=C(n+1,r)$

We have, $C(n,r)=\frac{n!}{(n-r)!\,r!}$ and, $C(n,r-1)=\frac{n!}{(n-r+1)!\,(r-1)!}$ Now, $\begin{array}{l} C(n,r)+C(n,r-1) &= \frac{n!}{(n-r)!\,(r-1)!}\left[\frac{1}{r}+\frac{1}{n-r+1}\right] \\ &= \frac{n!}{(n-r)!\,(r-1)!}\;\frac{n+1}{r(n-r+1)} \\ &= \frac{(n+1)!}{(n-r+1)!\,r!} \\ &= C(n+1,r) \end{array}$ $\therefore C(n,r)+C(n,r-1)=C(n+1,r)$

#### Example 1: Find the number of ways in which a student can select $5$ courses out of $8$ courses. If $3$ courses are compulsory, in how many ways can the selection be made?

The total number of ways in which the student can select $5$ courses out of $8$ courses is $\begin{array}{l} C(8,5) &= \frac{8!}{(8-5)!\,5!} \\ &= \frac{8!}{3!\,5!} \\ &= 56\;\text{ways} \end{array}$

If three courses are compulsory, then he has to select $2$ courses out of $5$ courses. Hence, the total number of ways the selection can be made is given by $\begin{array}{l} C(5,2) &= \frac{5!}{(5-2)!\,2!} \\ &= \frac{5!}{3!\,2!} \\ &= 10\;\text{ways} \end{array}$

Example 2: From $6$ gentlemen and $4$ ladies, a committee of $5$ is to be formed. In how many ways can this be done so as yo include at least one lady?

The selection of the members in the committee can be made as follows:

Thus, the required number of committee $\begin{array}{l} = ^4C_1×^6C_4+^4C_2×^6C_3+^4C_3×^6C_2+ ^4C_4×^6C_1 \\ = 4×15+6×20+4×15+1×6 \\ = 246 \end{array}$

Previous: Permutation