Combinations as Selections

Go back to  'Combinatorics'

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.

  1. 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.
  2. 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)!}}\).
  3. 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.
  4. 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.
  5. 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}\]

Learn math from the experts and clarify doubts instantly

  • Instant doubt clearing (live one on one)
  • Learn from India’s best math teachers
  • Completely personalized curriculum