Background
I have been teaching high school students for a while now. While I have taught physics and theory of knowledge, my main focus has been mathematics. One of the more fascinating areas of the high school mathematics syllabus is probability and statistics. Now don’t get me wrong. I know that, in an earlier post, I bemoaned the early inclusion of statistics, especially when it is done only to justify the use of a calculator. I have not changed my position on that. I still believe that many of our syllabuses, especially those that come from the Western hemisphere, are artificially bloated with topics that require the use of calculators, a move that reduces the priority of conceptual understanding in favor of brute force methods.
Indeed, it is precisely a method used in the area of probability and statistics that demonstrates how there is elegance in one approach to problem solving that is completely absent in another. The method I am referring to is commonly known as Combinatorial Proofs or Combinatorial Arguments.
The Meaning of ‘Combinatorics’
Now, many of you may be wondering what in the world ‘combinatorial’ means. Combinatorics is the branch of mathematics that deals with grouping of elements of finite sets of objects. Specifically, combinatorics is concerned with the number of such groups that can be formed rather than the groups per se. So, for example, if we have a set
Then the subsets with exactly 2 elements are
While I have considered the elements of the set to be the first three natural numbers, there is no reason we cannot extend this idea to any set with 3 distinct elements. Hence, in general we can say that, given a set containing 3 distinct elements, there are 3 ways to form a subset with exactly 2 elements. Another way of stating this is that the number of ways of selecting 2 out of 3 distinct objects is 3.
Backtracking a Bit
We have seen this idea before. In a post on fractions, I introduced the idea that the number of ways of selecting r out of n distinct items is
We revisited this idea in a post on the number e, in which we obtained the lower and upper bounds for e.
Using the above formula, we can prove some crucial results. For example, let us prove that
We can proceed as follows:
Or let us prove that
We can proceed as follows
Here, the proof depends, in large part, on our ability to recognize that the expression in red is common in both terms, allowing us to consider it a factor of the entire expression. However, this is not necessarily obvious. And unless one has developed some skill with manipulating binomial coefficients, it is unlikely one would be able to identify that such an expression actually is common to both terms.
The two ‘equations’ we have proved are known as ‘’binomial’ identities because they involve the coefficients that arise from the binomial expansion. Some of them can be quite difficult to prove using the brute force method of substituting the formula for nCr and then manipulating the various expressions. However, the method of using combinatorial arguments allows us to make logical arguments to prove the result. This actually gives us the insight about why the identity exists, which the brute force method cannot do – or at least cannot easily do.
Selection Equals Unselection
Suppose we have to prove that
using combinatorial arguments.
We can argue 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,
What this means is that selecting r out of n things or n-r items out of n things can be done in the same number of ways. Alternatively, we could say that the number of r member committees that can be formed from n candidates is the same as the number of n-r member committees that can be formed from the same n candidates.
Included or Excluded
Suppose we have to prove that
using combinatorial arguments.
We can argue as follows. Suppose we have n+1 items and we have to select r of them. This can obviously be done in n+1Cr ways. Now let us focus on any one of the n+1 items and let us call it item X. Now there are two cases. Either X is in our final selection or X is not. If X is not, then we still have to select r items from the remaining n items, which can obviously be done in nCr ways. If X is in the final selection, then we have to select r-1 items from the remaining n items, which can obviously be done in nCr-1 ways.
Since in both cases we end up selecting r items out of n+1 items it follows that
In other words, the number of ways of selecting r items out of n+1 items equals the sum of the number of ways of selecting r items out of n items, excluding one particular item, and the number of ways of selecting r-1 items out of n items, including the same item.
Committees and Sub-committees
Suppose we have to prove that
using combinatorial arguments.
We could argue 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 that we originally selected. This can be done in rCk ways. The two selections can obviously be done in nCr×rCk ways.
However, 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,
In other words, the number of ways of forming a committee, with r members, with a sub-committee, with k members, is equal to the number of ways of first forming the sub-committee, of k members, and then selecting the r-k members of the committee who are not a part of the sub-committee from the remaining unselected n-k members.
Wrapping Up
Now it is true that the combinatorial arguments do not give us any idea about how many ways the selection can be done. In that sense, they are deficient. However, the combinatorial arguments give us a clear understanding of how we can go about counting some specified subsets of a given set. The insights gained by the combinatorial arguments allow us to understand how best to enumerate sets so as to avoid double-counting and omission. This is not possible with a formula because much is lost when we express things in a compact formula. The frugality and austerity of mathematics itself causes things to become opaque. By using logical proofs, such as those involved in the combinatorial arguments, we can understand how the results we memorize come about. Unfortunately, because we all too often want a numerical answer to a question, we do not spend much time teaching and learning such elegant forms of argumentation. But by doing so we miss out on yet another factor that gives rise to beauty in mathematics.
Leave a comment