14.10: Combinatorial Proofs
- Page ID
- 48402
Suppose you have \(n\) different T-shirts, but only want to keep \(k\). You could equally well select the \(k\) shirts you want to keep or select the complementary set of \(n - k\) shirts you want to throw out. Thus, the number of ways to select \(k\) shirts from among \(n\) must be equal to the number of ways to select \(n-k\) shirts from among \(n\). Therefore:
\[\nonumber {n \choose k} = {n \choose n-k}.\]
This is easy to prove algebraically, since both sides are equal to:
\[\nonumber \dfrac{n!}{k! (n-k)!}.\]
But we didn’t really have to resort to algebra; we just used counting principles.
Hmmm....
Pascal’s Triangle Identity
Bob, famed Math for Computer Science Teaching Assistant, has decided to try out for the US Olympic boxing team. After all, he’s watched all of the Rocky movies and spent hours in front of a mirror sneering, “Yo, you wanna piece a’ me?!” Bob figures that \(n\) people (including himself) are competing for spots on the team and only \(k\) will be selected. As part of maneuvering for a spot on the team, he needs to work out how many different teams are possible. There are two cases to consider:
- Bob is selected for the team, and his \(k-1\) teammates are selected from among the other \(n-1\) competitors. The number of different teams that can be formed in this way is:
\[\nonumber {n-1 \choose k-1}.\]
- Bob is not selected for the team, and all \(k\) team members are selected from among the other \(n-1\) competitors. The number of teams that can be formed this way is:
\[\nonumber {n-1 \choose k}.\]
All teams of the first type contain Bob, and no team of the second type does; therefore, the two sets of teams are disjoint. Thus, by the Sum Rule, the total number of possible Olympic boxing teams is:
\[\nonumber {n-1 \choose k-1} + {n-1 \choose k}.\]
Ted, equally-famed Teaching Assistant, thinks Bob isn’t so tough and so he might as well also try out. He reasons that \(n\) people (including himself) are trying out for \(k\) spots. Thus, the number of ways to select the team is simply:
\[\nonumber {n \choose k}.\]
Ted and Bob each correctly counted the number of possible boxing teams. Thus, their answers must be equal. So we know:
Lemma 14.10.1 (Pascal’s Triangle Identity).
\[\label{14.10.1} {n \choose k} = {n-1 \choose k-1} + {n-1 \choose k}\]
We proved Pascal’s Triangle Identity without any algebra! Instead, we relied purely on counting techniques.
Giving a Combinatorial Proof
A combinatorial proof is an argument that establishes an algebraic fact by relying on counting principles. Many such proofs follow the same basic outline:
- Define a set \(S\).
- Show that \(|S| = n\) by counting one way.
- Show that \(|S| = m\) by counting another way.
- Conclude that \(n = m\).
In the preceding example, \(S\) was the set of all possible Olympic boxing teams. Bob computed
\[\nonumber |S| = {n-1 \choose k-1} + {n-1 \choose k}\]
by counting one way, and Ted computed
\[\nonumber |S| = {n \choose k} \]
by counting another way. Equating these two expressions gave Pascal’s Identity.
Checking a Combinatorial Proof
Combinatorial proofs are based on counting the same thing in different ways. This is fine when you’ve become practiced at different counting methods, but when in doubt, you can fall back on bijections and sequence counting to check such proofs.
For example, let’s take a closer look at the combinatorial proof of Pascal’s Identity (\ref{14.10.1}). In this case, the set \(S\) of things to be counted is the collection of all size-\(k\) subsets of integers in the interval \([1..n]\).
Now we’ ve already counted \(S\) one way, via the Bookkeeper Rule, and found \(|S| = {n \choose k}\). The other “way” corresponds to defining a bijection between \(S\) and the disjoint union of two sets \(A\) and \(B\) where,
\[\begin{aligned} A &::= \{(1, X) \mid X \subseteq [2, n] \text{ AND } |X| = k - 1\} \\ B &::= \{(0, Y) \mid Y \subseteq [2, n] \text{ AND } |Y| = k\} \end{aligned}\]
Clearly \(A\) and \(B\) are disjoint since the pairs in the two sets have different first coordinates, so \(|A \cup B| =|A| + |B|\). Also,
\[\nonumber |A| = \text{# specified sets } X = {n-1 \choose k-1}.\]
\[\nonumber |B| = \text{# specified sets } Y = {n-1 \choose k}.\]
Now finding a bijection \(f : (A \cup B) \rightarrow S\) will prove the identity (\ref{14.10.1}). In particular, we can define
\[\nonumber f(c)::=\left\{\begin{array}{ll} X \cup \{1\} & \text { if } c =(1, X), \\ Y & \text { if } c =(0, Y). \end{array}\right.\]
It should be obvious that \(f\) is a bijection.
Colorful Combinatorial Proof
The set that gets counted in a combinatorial proof in different ways is usually defined in terms of simple sequences or sets rather than an elaborate story about Teaching Assistants. Here is another colorful example of a combinatorial argument.
Theorem \(\PageIndex{2}\)
\[\nonumber \sum_{r = 0}^{n} {n \choose r} {2n \choose n-r} = {3n \choose n}\]
- Proof
-
We give a combinatorial proof. Let \(S\) be all \(n\)-card hands that can be dealt from a deck containing \(n\) different red cards and \(2n\) different black cards. First, note that every \(3n\)-element set has
\[\nonumber |S| = {3n \choose n}\]
\(n\)-element subsets.
From another perspective, the number of hands with exactly \(r\) red cards is
\[\nonumber {n \choose r} {2n \choose n-r}\]
since there are \({n \choose r}\) ways to choose the \(r\) red cards and \({2n \choose n-r}\) ways to choose the \(n -r\) black cards. Since the number of red cards can be anywhere from 0 to \(n\), the total number of n-card hands is:
\[\nonumber |S| = \sum_{r = 0}^{n} {n \choose r} {2n \choose n-r}.\]
Equating these two expressions for \(|S|\) proves the theorem. \(\quad \blacksquare\)
Finding a Combinatorial Proof
Combinatorial proofs are almost magical. Theorem 14.10.2 looks pretty scary, but we proved it without any algebraic manipulations at all. The key to constructing a combinatorial proof is choosing the set \(S\) properly, which can be tricky. Generally, the simpler side of the equation should provide some guidance. For example, the right side of Theorem 14.10.2 is \({3n \choose n}\), which suggests that it will be helpful to choose \(S\) to be all \(n\)-element subsets of some \(3n\)-element set.