Combinations (Part 3)


In this lesson you’ll learn a result about binomial coefficients: \( {}^{n}C_r ={}^{n}C_{n-r} \), using the formula as well as by using combinations.

For example \( {}^{7}C_2 \) equals \( {}^{7}C_{7-2}  \) or \( {}^{7}C_5 \).

Lets calculate to be sure.

\( {}^{7}C_2 = \frac{7!}{2!(7-2)!} = \frac{7.6.5.4.3.2.1}{(2.1)(5.4.3.2.1)} = 21 \) and \( {}^{7}C_5 = \frac{7!}{5!(7-5)!} = \frac{7.6.5.4.3.2.1}{(5.4.3.2.1)(2.1)} = 21 \)

Observe that the “2!” and the “5!” just got exchanged, while the numerator remains the same. Can you see why this will hold true for all kinds of \( {}^{n}C_r \)s in general ?

If not, here’s why. Using the formula for \( {}^{n}C_r \), which equals \(  \frac{n!}{r!(n-r)!} \), we have \( {}^{n}C_{n-r} = \frac{n!}{(n-r)!(n-(n-r))!} = \frac{n!}{(n-r)!(r)!} = \frac{n!}{r!(n-r)!}={}^{n}C_r \)

In other words, the r! and (n-r)! get interchanged, and the expression’s value remains the same.

Okay, now there’s another way we can reach the same result. Recall that \( {}^{n}C_r \) is the number of ways to select r objects from n different objects.

To prove that \( {}^{n}C_r ={}^{n}C_{n-r} \), we have to argue that the number of ways to select r objects from n different objects should be the same as the number of ways to select n – r objects from n different objects.

As an example, suppose we are to select 3 letters from out of  the 4 letters A,B,C and D. To select the letters, we line up the 4 letters, and make the selections by circling out any 3 of these 4 letters. Here are the possible selections..

combinations

There are 4 possible selections (which is same as \( {}^{4}C_3 \), as derived earlier). Now to make the same selections, we could do the following instead..

combinations

That is, put a cross mark on that letter, which is not to be selected. And in how many ways can we do that? In \( {}^{4}C_1 \) ways! Why? Because out of 4 letters you’ve to select 1 (and put a cross on it).

So the selection of 3 letters out of 4 can be done by putting a circle each on 3 of the letters to be selected OR by putting a cross on the letter not to be selected. That is, selecting 3 objects (out of 4) is exactly the same as selecting 1 object (and throwing it away, thereby selecting the remaining 3 objects).

Well? This means that \( {}^{4}C_3 \) must equal  \( {}^{4}C_{1} \), as we’re essentially doing the same thing in both these methods (which should make the number of ways of both the methods equal)

To generalize, selecting r things out of n different things is exactly same as selecting n – r things and removing them from the lot, so the remaining r things get automatically selected. Therefore, the number of ways to the former, i.e. \( {}^{n}C_r \) must equal the number of ways to do the latter, i.e. \( {}^{n}C_{n-r} \)

And phew ! We’re done ! \( {}^{n}C_r ={}^{n}C_{n-r} \)

Lesson Summary

nCr = nCn – r

I’ll move on to some examples related to combinations in the next lesson.

PS: The second method of proving is known as a combinatorial argument / proof. We’ll use similar methods to find sums of a few strange looking series. As an exercise, try proving \( {}^{n}C_r + {}^{n}C_{r-1} = {}^{n+1}C_r \) using both methods.


Leave a comment

One thought on “Combinations (Part 3)