# Combinations

Consider the word EDUCATION. This has 9 distinct letters. How many 3-letter permutations (words) can be formed using the letters of this word? We now know how to answer questions like this; the answer in this particular case will be \(^9{P_3}\).

However, suppose that instead of 3-letter *arrangements*, you are asked to count the number of 3-letter *selections*. How will your answer change?

Consider the following 3-letter permutations formed using the letters A, E, T from EDUCATION:

AET ATE

EAT ETA

TAE TEA

These 6 *different* *arrangements* correspond to the *same selection* of letters, which is {A, E, T}. Thus, in the list of all 3-letter permutations, we will find that each unique selection corresponds to 6 different arrangements. To find the number of unique 3-letter selections, we divide the number of 3-letter permutations by 6.

Hence, the number of 3-letter selections will be \(\frac{{^9{P_3}}}{6}\).

Let us generalize this. Suppose that you have *n* different objects. You have to determine the number of unique *r*-selections (selections which contain *r* objects) which can be made from this group of *n* objects. Think of a group of *n* people – you have to find the number of unique sub-groups of size *r*, which can be created from this group.

The number of permutations of size *r* will be \(^n{P_r}\). In the list of \(^n{P_r}\) permutations, each unique selection will be counted \(r!\) times, because the objects in an *r*-selection can be permuted amongst themselves in \(r!\) ways. Thus, the number of unique selections will be \(\frac{{^n{P_r}}}{{r!}}\).

A selection is also called a *combination*. We denote the number of unique *r*-selections or combinations (out of a group of *n* objects) by \(^n{C_r}\). Thus,

\[^n{C_r} = \frac{{^n{P_r}}}{{r!}} = \frac{{\left\{ {\frac{{n!}}{{\left( {n - r} \right)!}}} \right\}}}{{r!}} = \frac{{n!}}{{r!\left( {n - r} \right)!}}\]

Here are some examples:

(i) Out of a group of 5 people, a pair needs to be formed. The number of ways in which this can be done is

\[^5{C_2} = \frac{{5!}}{{2!\left( {5 - 2} \right)!}} = \frac{{5!}}{{2!3!}} = \frac{{120}}{{2 \times 6}} = 10\]

(ii) The number of 4-letter selections which can be made from the letters of the word DRIVEN is

\[^6{C_4} = \frac{{6!}}{{4!\left( {6 - 4} \right)!}} = \frac{{6!}}{{4!2!}} = \frac{{720}}{{24 \times 2}} = 15\]

(iii) The number of ways of selecting *n* objects out of *n* objects is

\[^n{C_n} = \frac{{n!}}{{n!\left( {n - n} \right)!}} = \frac{{n!}}{{n!0!}} = 1\]

The number of ways of selecting 0 objects out of *n* objects is:

\[^n{C_0} = \frac{{n!}}{{0!\left( {n - 0} \right)!}} = \frac{{n!}}{{0!n!}} = 1\]

The number of ways of selecting 1 object out of *n* objects is:

\[^n{C_1} = \frac{{n!}}{{1!\left( {n - 1} \right)!}} = \frac{{n \times \left( {n - 1} \right)!}}{{\left( {n - 1} \right)!}} = n\]

These results are intuitively obvious.

(iv) The number of ways of selecting 2 objects out of *n* is

\[\begin{align}&{}^nC_2=\frac{n!}{2!\left(n-2\right)!}=\frac{n\times\left(n-1\right)\times\left(n-2\right)!}{2\left(n-2\right)!}\\&\qquad\qquad\qquad\qquad=\frac{n\left(n-1\right)}2\end{align}\]

We now summarize our discussion on combinations up to this point.

- Just like you associated the word
*permutations*with the word*arrangements*, you should associate the word*combinations*with the word*selections*. Whenever you read the phrase “number of combinations”, think of the phrase “number of selections”. When you are selecting objects, the order of the objects*does not matter*. For example, XYZ and XZY are different arrangements, but the same selection. - The number of combinations of
*n*distinct objects, taken*r*at a time (where*r*is less than*n*), is \(^n{C_r} = \frac{{^n{P_r}}}{{r!}} = \frac{{n!}}{{r!\left( {n - r} \right)!}}\). - This result above is derived from the fact that in the list of all permutations of size
*r*, each unique selection is counted \(r!\) times. - Out of
*n*objects, the number of ways of selecting 0 or*n*objects is 1; the number of ways of selecting 1 object is*n*. - Out of
*n*objects, the number of ways of selecting 2 objects is \(^n{C_2} = \frac{{n\left( {n - 1} \right)}}{2}\).

We will now apply these results to some examples. Before that, we once again highlight the following association:

\[\begin{align}&

{\rm{PERMUTATIONS }} \equiv {\rm{ARRANGEMENTS}}\\

\\&

{\rm{COMBINATIONS }} \equiv {\rm{ SELECTIONS}}

\end{align}\]