14.1: Counting One Thing by Counting Another

How do you count the number of people in a crowded room? You could count heads, since for each person there is exactly one head. Alternatively, you could count ears and divide by two. Of course, you might have to adjust the calculation if someone lost an ear in a pirate raid or someone was born with three ears. The point here is that you can often count one thing by counting another, though some fudging may be required. This is a central theme of counting, from the easiest problems to the hardest. In fact, we’ve already seen this technique used in Theorem 4.5.5, where the number of subsets of an \(n\)-element set was proved to be the same as the number of length-\(n\) bit-strings, by describing a bijection between the subsets and the bit-strings.

The most direct way to count one thing by counting another is to find a bijection between them, since if there is a bijection between two sets, then the sets have the same size. This important fact is commonly known as the Bijection Rule. We’ve already seen it as the Mapping Rules bijective case (4.5.3).

The Bijection Rule

The Bijection Rule acts as a magnifier of counting ability; if you figure out the size of one set, then you can immediately determine the sizes of many other sets via bijections. For example, let’s look at the two sets mentioned at the beginning of Part III:

\[\begin{aligned} A &= \text{all ways to select a dozen donuts when five varieties are available} \\ B &= \text{all 16-bit sequences with exactly 4 ones} \end{aligned}\]

An example of an element of set \(A\) is:

\[\nonumber \underbrace{00}_{\text {chocolate }} \underbrace{ }_{\text {lemon-filled }} \underbrace{000000}_{\text {sugar }} \underbrace{00}_{\text {glazed }} \underbrace{00}_{\text {plain }}\]

Here, we’ve depicted each donut with a 0 and left a gap between the different varieties. Thus, the selection above contains two chocolate donuts, no lemon-filled, six sugar, two glazed, and two plain. Now let’s put a 1 into each of the four gaps:

\[\nonumber \underbrace{00}_{\text {chocolate }} 1 \underbrace{ }_{\text {lemon-filled }} 1 \underbrace{000000}_{\text {sugar }} 1 \underbrace{00}_{\text {glazed }} 1 \underbrace{00}_{\text {plain }}\]

and close up the gaps:

0011000000100100.

We’ve just formed a 16-bit number with exactly 4 ones—an element of \(B\)!

This example suggests a bijection from set \(A\) to set \(B\): map a dozen donuts consisting of:

\(c\) chocolate, \(l\) lemon-filled, \(s\) sugar, \(g\) glazed, and \(p\) plain

to the sequence:

\[\nonumber \underbrace{0 \cdots 0}_{c} 1 \underbrace{0 \cdots 0}_{l} 1 \underbrace{0 \cdots 0}_{s} 1 \underbrace{0 \cdots 0}_{g} 1 \underbrace{0 \cdots 0}_{p}\]

The resulting sequence always has 16 bits and exactly 4 ones, and thus is an element of \(B\). Moreover, the mapping is a bijection: every such bit sequence comes from exactly one order of a dozen donuts. Therefore, \(|A| = |B|\) by the Bijection Rule. More generally,

Lemma 14.1.1. The number of ways to select \(n\) donuts when \(k\) flavors are available is the same as the number of binary sequences with exactly \(n\) zeroes and \(k - 1\) ones.

This example demonstrates the power of the bijection rule. We managed to prove that two very different sets are actually the same size—even though we don’t know exactly how big either one is. But as soon as we figure out the size of one set, we’ll immediately know the size of the other.

This particular bijection might seem frighteningly ingenious if you’ve not seen it before. But you’ll use essentially this same argument over and over, and soon you’ll consider it routine.