Recall in our previous readings how we derived the number of \(k\)-subsets drawn from \(n\) elements, \(n \choose k\):
Generate an ordered sequence of size \(k\) drawn from \(n\) elements, \((n)_k\) such sequences in all. For every unique subset of \(k\) elements, remove the \(k!\) permutations of that subset that appear in the set of ordered sequences. What remains is a subset of size \(k\) drawn from the \(n\) elements. Therefore, \({n \choose k} = \frac{(n)_k}{k!}\).
This is not the only way that we can derive \(n \choose k\). Consider this alternative derivation.
Generate an ordered sequence of size \(n\), \(n!\) such sequences in all and select the first \(k\) elements from the sequence to be a subset. Observe that once we have distinguished the first \(k\) elements from the remaining \(n-k\) elements of the sequence, the first \(k\) elements can be permuted in \(k!\) ways, and the remaining elements can be permuted in \((n-k)!\) ways. Therefore, for every such unique subset of \(k\) elements, remove the \(k!(n-k)!\) equivalent sequences that contain this subset. Thus, \({n \choose k} = \frac{n!}{k!(n-k)!}\).
Observe that from both derivations we can conclude that:
\[ {n \choose k} = \frac{(n)_k}{k!} = \frac{n!}{k!(n-k)!} \]
In other words, if we can count a collection of objects in two different ways, those two different ways must be equal. This is the principle of double-counting: two arithmetic formulae are equal if they count the same collection of objects.
As a second example, let’s consider the following combinatorial identity:
\[ {n \choose k} = {n \choose n-k}. \]
We could use arithmetic to demonstrate this identity. However, let’s use double-counting instead, which will immediately unveil why the two quantities are equivalent. To do so, we must demonstrate that both formulae count the same object. It is clear from the left-hand side that the quantity in question is likely the number of \(k\)-sized subsets drawn from \(n\) elements. The left-hand side is precisely this quantity, so we must argue that the right-hand also computes this quantity.
Claim: the number of \(k\)-sized subsets drawn from \(n\) elements is \(n \choose n-k\).
Proof. Observe that \(n \choose n-k\) is the number of possible subsets of size \(n-k\). Consider such a subset and note that \(k\) elements are not included in this subset. The elements not included in the \(n-k\) subset form the \(k\)-sized subset in question. Finally, because we consider all such possible \(n-k\)-sized subsets, then we will also consider all \(k\)-sized subsets in this manner.
Because we demonstrated that the two formulae count the same collection—the number of \(k\)-subsets drawn from \(n\) elements—we can conclude that they are equal.
Also, note that this particular example is interesting because it demonstrates yet another counting technique: implicit counting. Sometimes it is difficult to construct an object directly. Instead, we can construct another object that implies the desired object. Here, we constructed \(n-k\) subsets whose existence implied the \(k\)-sized subset we wanted.
Exercise (The One-two Punch, ‡): use the double-counting principle to justify this equality:
\[ {n+m \choose n} = {n+m \choose m}. \]
To do so, identify the collection of objects the two formulae are counting. Then describe how the left- and right-hand sides of the equality count that collection.