Recapitulation
In this post we continue with the series on Counting Principles. Whereas we devoted the previous post to permutations of special kinds, we will turn our attention today to the matter of combinations. In Arranging and Choosing we saw that the binomial coefficients are related to the elements of Pascal’s triangle. We saw that the process of expanding an expression like (a + b)n involves multiplying a + b by itself n times. This involves choosing either a or b from each factor. We were, therefore, able to show that the (r + 1)th element of the nth row of Pascal’s triangle is the sum of the rth element of the (n – 1)th row and the (r + 1)th element of the (n – 1)th row. In symbolic notation,
While we proved this result with algebra, I claimed that the algebraic method, involving pure brute force of algebraic manipulation, did not yield any particular insight. However, we proved the above result using
and arguing from how a particular element on the left side is obtained by adding two terms on the right side. This sort of argumentation does not use algebra. However, the argument in Arranging and Choosing is not technically what is called a ‘combinatorial argument’. So, what is a combinatorial argument? Let us learn with a few examples.
Combinatorial Arguments
Example 1
We begin with the same result we proved earlier. Suppose we have n distinct items and we wish to choose r out of them. This can obviously be done in nCr ways. Now, let us focus on one particular item (say A) out of the n items. The group of r items that are selected either contains A or does not contain A. If the selection contains A, then we have to choose r – 1 more items from the remaining n – 1 items, which can be done in n – 1Cr – 1 ways. If the selection does not contain A, then we still have to choose r items from the remaining n – 1 items, which can be done in n – 1Cr ways. Since the selections that contain A and do not contain A are mutually exclusive (meaning they have no common members) and exhaustive (meaning that there are no other possibilities), it follows that
As an example, suppose we have to choose 6 items out of 20. This can be done in 20C6 = 38,760 ways. Now, if one of the items is A, then the selection either contains A or does not contain A. If it contains A, then we have to select 5 more items from the remaining 19 items, which can be done in 19C5 = 11,628 ways. If it does not contain A, then we have to select 6 items from the remaining 19 items, which can be done in 19C6 = 27,132 ways. It is easy to check that 11,628 + 27,132 = 38,760. This is an example of the addition principle that we dealt with in Down for the Count.
Example 2
Let us consider another result, namely
We proceed as follows. Suppose we have n items and we have to select r of them for some purpose. This obviously can be done in nCr ways. However, by selecting the r items for the purpose, we automatically create a selection of the remaining n – r items not for that purpose – that is for some other purpose. Selecting n – r items for some other purpose can obviously be done in nCn – r ways. Since the selection of r items automatically creates a selection of the remaining n – r items, the number of ways must be equal. Hence, nCr = nCn – r .
Example 3
Now let us try to prove
We proceed as follows. Suppose we have n items from which we have to select r items. This can be done in nCr ways. Now suppose we select k items from the r. This can be done in rCk ways. The two selections can obviously be done in nCr rCk ways. But we can make these selections in a different way. Let us first select the k items from the original n items. This can be done in nCk ways. Now we have to select r – k items from the remaining n – k items, which can be done in n – kCr – k ways. The two selections can obviously be done in nCk n – kCr – k ways. Since in both cases we end up with r – k items for one purpose and k items for a second purpose, the number of ways must be the same. Hence, nCr rCk = nCk n – kCr – k.
An example of this last result is as follows. Suppose we have a class of 30 students. We need to select a committee of 7 members within which we select a sub-committee of 3 members. Then we can first select the entire committee, which can be done in 30C7 = 2,035,800 ways. Then we select the sub-committee, which can be done in 7C3 = 35 ways. This gives a total of 2,035,800 × 35 = 71,253,000 ways. Alternately, we select the sub-committee first, which can be done in 30C3 = 4,060 ways. Now we have to choose the remaining 4 members of the committee from the remaining 27 students, which can be done in 27C4 = 17,550 ways. This gives a total of 4,060 × 17,550 = 71,253,000 ways. This is an example of the multiplication principle that we dealt with in Down for the Count.
Binomial Identities
Having considered some combinatorial arguments, we turn our attention to the binomial coefficients themselves. Since there is a pattern leading from one row to the next, there must be some relationships that hold among these coefficients. For simplicity in proposing and proving these relationships, let us take a = 1 and b = x in the expansion of (a + b)n, which becomes (1 + x)n.
Example 1
Using the normal binomial expansion we obtain
If we substitute x = 1 in the above we get
We can verify this by considering a few rows of Pascal’s triangle. For example
We can see that the identity holds true for the first 5 values of n.
Example 2
Now, if we substitute x = -1 in the expansion of (1 + x)n, we will get
We can verify this for the first few rows of Pascal’s triangle. For example
Again, we can see that the identity holds true for the first 5 values of n.
Example 3
We can even use differentiation to obtain various results. For example, consider the expansion
If we differentiate both sides with respect to x we will get
Now, if we substitute x = 1 in the above equation, we will get
Again, we can verify this for the first few rows of Pascal’s triangle. For example
Once again, we have seen that the derived identity holds for the first 5 values of n.
Example 4
We can carry the idea of differentiation further as follows. We know that
If we multiply both sides by x we will get
Now, if we differentiate with respect to x we will get
Once again, we can verify this for the first few rows of Pascal’s triangle. For example
So, we have verified the result for the first 3 rows of Pascal’s triangle.
Parting Shot
What we have seen in this post is that we can use logical arguments to obtain relationships between binomial coefficients. We can also use simple algebra and calculus to obtain other relationships. As seen in the last example, we can multiple (1 + x)n by other terms to obtain further identities. The results are quite obviously endless. For example, I leave the reader to attempt to prove that
Perhaps a hint would help. Consider the expansion of
If you wish to check the proof, click here.
Our study of counting principles is not over, though. There is much more left to go. In the next post, we will consider how to obtain the number of divisors and sum of the divisors of any natural number without actually listing the divisors or counting them. And we will consider the technique of partitions. Till then, the ball is in your court.
Acutely Obtuse 
Leave a comment