This lesson will show you another way to count the number of different possible selections or combinations of distinct objects.
Consider 6 different objects: A, B, C, D, E and F
Now suppose we have to select 1 object from the lot. Clearly, we have 6 different possible selections: A, B, C, D, E or F. This is same as \( {}^{6}C_1 \) as we derived in the previous lesson.
Okay, what if we have to select 2 objects? First we’ll select any 1 object in \( {}^{6}C_1 \) ways. Now there are 5 objects remaining, of which we have to select 1 more. This can be done in 5 ways. So the total number of ways to complete the selection will be \( {}^{6}C_1 \) x 5.
But there is a problem. In the above way of calculating, we’ve counted “selecting A followed by B” and “selecting B followed by A” as different. But they are the same, as the order of selection does not matter. We’ve counted the same selection twice.
Therefore to arrive at the correct answer we’ll have to divide the previous answer by 2. Therefore the total number of selections will be (\( {}^{6}C_1 \) x 5)/2.
This is same as \( \frac{6!}{5!1!} \times \frac{5}{2} = \frac{6!}{4!2!} = {}^{6}C_2 \).
What about 3 objects? First, select any 2: \( {}^{6}C_2 \) ways. Then out of the remaining 4, select any 1: 4 ways. Now again if we multiply \( {}^{6}C_2 \) by 4, we would have counted each selection thrice (A,B followed by C; A,C followed by B; B,C followed by A). So we’ll have to divide the product by 3: (\( {}^{6}C_2 \times 4)/3 = \frac{6!}{2!4!} \times \frac{4}{3} = \frac{6!}{3!3!} = {}^{6}C_3 \). Same answer as we derived earlier!
I think we can now generalise this logic to n objects, inductively. If we know the way to select ‘r – 1’ objects the number of way to select ‘r’ objects will be obtained by multiplying the previous by (n – (r – 1)) (as there will be these many objects left after we’ve selected ‘r – 1’, and we’ve to select 1 more) and then dividing by r (as each selection will be repeated r times, as we saw above)
The number of ways to select 1 object = n or \( {}^{n}C_1 \).
The number of ways to select 2 objects will be \( {}^{n}C_1 \times \frac{n – 1}{2} = \frac{n!}{1!(n – 1)!} \times \frac{n – 1}{2} = \frac{n!}{2!(n – 2)!} = {}^{n}C_2 \)
The number of ways to select 3 objects will be \( {}^{n}C_2 \times \frac{n – 2}{3} = \frac{n!}{2!(n – 2)!} \times \frac{n – 2}{3} = \frac{n!}{3!(n – 3)!} = {}^{n}C_3 \)
The number of ways to select 4 objects will be \( {}^{n}C_3 \times \frac{n – 3}{4} = \frac{n!}{3!(n – 3)!} \times \frac{n – 3}{4} = \frac{n!}{4!(n – 4)!} = {}^{n}C_4 \)
And so on… I hope you get the idea.
We’ve reached the same expression/formula – \( {}^{n}C_r \) – to obtain the number of selections of r objects from n distinct objects, using a different logic. (There might be many more.)
See you in the next lesson !
Lesson Summary
The number of ways of selecting r objects out of n distinct objects is given by \( {}^{n}C_r \), which equals \( \frac{n!}{(n-r)!r!} \)
PS: The numbers \( {}^{6}C_2 \), \( {}^{10}C_7 \), \( {}^{n}C_r \) etc are referred to as ‘binomial coefficients’. Details here.