4.2: Combinatorial Proofs

As we said in the previous section, thinking about a problem in two different ways implicitly creates a bijection, telling us that the number of solutions we obtain will be the same either way. When we looked at bijections, we were using this idea to find an easier way to count something that seemed difficult. But if we actually can find a (possibly messy) formula that counts the answer to our problem correctly in some “difficult” way, and we can also find a different formula that counts the answer to the same problem correctly by looking at it in a different way, then we know that the values of the two formulas must be equal, no matter how different they may look.

This is the idea of a “combinatorial proof".

Theorem \(\PageIndex{1}\)

If \(f(n)\) and \(g(n)\) are functions that count the number of solutions to some problem involving \(n\) objects, then \(f(n) = g(n)\) for every \(n\)

Definition: Combinatorial Identity

Suppose that we count the solutions to a problem about \(n\) objects in one way and obtain the answer \(f(n)\) for some function \(f\); and then we count the solutions to the same problem in a different way and obtain the answer \(g(n)\) for some function \(g\). This is a combinatorial proof of the identity \(f(n) = g(n)\).

The equation \(f(n) = g(n)\) is referred to as a combinatorial identity.

In the statement of this theorem and definition, we’ve made \(f\) and \(g\) functions of a single variable, \(n\), but the same ideas hold if \(f\) and \(g\) are functions of more than one variable. Our first example demonstrates this.

Example \(\PageIndex{1}\)

Prove that for every natural number \(n\) and every integer \(r\) between \(0\) and \(n\), we have

\(\binom{n}{r} = \binom{n}{n-r}\)

Solution

By the definition of \(\binom{n}{r}\), this is the number of ways of choosing \(r\) objects from a set of \(n\) distinct objects. Any time we choose \(r\) of the objects, the other \(n − r\) objects are being left out of the set we are choosing. So equivalently, instead of choosing the \(r\) objects to include in our set, we could choose the \(n − r\) objects to leave out of our set. By the definition of the binomial coefficients, there are \(\binom{n}{n-r}\) ways of making this choice.

Therefore, it must be the case that for every natural number \(n\) and every integer \(r\) between \(0\) and \(n\), we have

\(\binom{n}{r} = \binom{n}{n-r}\)

as desired,

Of course, this particular identity is also quite easy to prove directly, using the formula for \(\binom{n}{r}\), since

\(\binom{n}{n-r} = \dfrac{n!}{(n-r)!(n-(n-r))!} = \dfrac{n!}{(n-r)!r!} = \binom{n}{r} \)

Many identities that can be proven using a combinatorial proof can also be proven directly, or using a proof by induction. The nice thing about a combinatorial proof is it usually gives us rather more insight into why the two formulas should be equal, than we get from many other proof techniques.

In Example 4.1.1, we noted that one way to figure out the number of subsets of an n-element set would be to count the number of subsets of each possible size, and add them all up. We then followed a bijective approach to prove that the answer is in fact \(2n\). If we actually carry through on the first idea, this leads to another combinatorial identity (one that we already observed via the Binomial Theorem):

Example \(\PageIndex{2}\)

Prove that for every natural number \(n\)

\(\sum_{r=0}^{n} \binom{n}{r} = 2^n\)

Solution

We have seen in Example 4.1.1 that the number of subsets of a set of \(n\) elements is \(2^n\). We will count the same problem in a different way, to obtain the other side of the equality.

To determine the number of subsets of a set of \(n\) elements, we break the problem down into \(n + 1\) cases, and use the sum rule. The cases into which we will divide the problem are the different possible cardinalities for the subsets: everything from \(0\) through \(n\). There are \(\binom{n}{r}\) ways to choose a subset of \(r\) elements from the set of \(n\) elements, so the number of subsets that contain \(r\) elements is \(\binom{n}{r}\). Thus, the total number of subsets of our original set must be \(\sum_{r=0}^{n} \binom{n}{r}\).

Since we have counted the same problem in two different ways and obtained different formulas, Theorem 4.2.1 tells us that the two formulas must be equal; that is,

\(\sum_{r=0}^{n} \binom{n}{r} = 2^n\)

as desired.

We can also produce an interesting combinatorial identity from a generalisation of the problem studied in Example 4.1.2.

Example \(\PageIndex{3}\)

Suppose we have a collection of \(n\) men and \(n\) women, and we want to choose \(r\) of them for a focus group, but we must include at least one woman. In how many ways can this be done? Use two different methods to count the solutions, and deduce a combinatorial identity.

Solution

Using the same reasoning that we applied in Example 4.1.2, we see that the number of ways of choosing a group that includes at least one woman is the total number of ways of choosing a group of \(r\) people from these \(2n\) people, less the number of ways that include only men; that is: \(\binom{2n}{r} − \binom{n}{r}\).

Alternatively, we can divide the problem up into \(r\) cases depending on how many women are to be included in the group (there must be \(i\) women, for some \(1 ≤ i ≤ r\)). There are \(\binom{n}{i}\) ways to choose \(i\) women for the group, and for each of these, there are \(\binom{n}{r-i}\) ways to choose \(r−i\) men to complete the group. Thus, the total number of ways of choosing a group that includes at least one woman, is

\(\sum_{i=1}^{r} \binom{n}{i} \binom{n}{r - i}\)

This argument yields the combinatorial identity

\(\sum_{i=1}^{r} \binom{n}{i} \binom{n}{r - i} = \binom{2n}{r} - \binom{n}{r}\)

which we have thereby proven.

One context in which combinatorial proofs arise very naturally is when we are counting ordered pairs that have some property. That is, for some subset of \(X \times Y\), we may wish to count all of the ordered pairs \((x, y)\), where \(x ∈ X\) and \(y ∈ Y\), such that \((x, y)\) has some property. We can do this by first considering every possible value of \(x ∈ X\), and for each such value, counting the number of \(y ∈ Y\) such that \((x, y)\) satisfies the desired property, or by first considering every possible value of \(y ∈ Y\), and for each such value, counting the number of \(x ∈ X\) such that \((x, y)\) satisfies the desired property.

Although this idea may not seem very practical, it is actually the context in which many of the combinatorial proofs in later chapters will arise. We will be looking at a set \(X\) of elements, and a set \(Y\) that is actually a collection of subsets of elements of \(X\), and counting pairs \((x, y)\) for which the element \(x\) appears in the subset \(y\). By counting these pairs in two ways, we will find a combinatorial identity.

Example \(\PageIndex{4}\)

Let \(B\) be the set of city blocks in a small city, and let \(S\) be the set of street segments in the city (where a street segment means a section of street that lies between two intersections). Assume that each block has at least three sides. Count the number of pairs \((s, b)\) with \(s ∈ S\) and \(b ∈ B\) such that the street segment \(s\) is adjacent to the block \(b\) in two ways. Use this to deduce a combinatorial inequality.

Solution

Let \(|S| = t\). Each street segment is adjacent to two blocks: the blocks that lie on either side of the street. Therefore, for any given street segment \(s\), there are two pairs \((s, b)\) such that \(s\) is adjacent to the block \(b\). Multiplying this count by \(t\) (the number of street segments) tells us that the total number of pairs \((s, b) ∈ S \times B\) with \(s\) adjacent to \(b\) is \(2t\).

Let \(|B| = c\). Each block is adjacent to at least \(3\) street segments: the street segments that surround the block. Therefore, for any given block \(b\) in the city, there are at least \(3\) pairs \((s,b)\) such that \(b\) is adjacent to the street segment \(s\). Multiplying this count by \(c\) (the number of blocks) tells us that the total number of pairs \((s, b) ∈ S \times B\) with \(s\) adjacent to \(b\) is at least \(3c\).

We deduce that \(2t ≥ 3c\).

Exercise \(\PageIndex{1}\)

Let \(P\) be the set of people in a group, with \(|P| = p\). Let \(C\) be a set of clubs formed by the people in this group, with \(|C| = c\). Suppose that each club contains exactly \(g\) people, and each person is in exactly \(j\) clubs. Use two different ways to count the number of pairs \((b, h) ∈ P \times C\) such that person \(b\) is in club \(h\), and deduce a combinatorial identity.

Exercise \(\PageIndex{2}\)

Prove the following combinatorial identities, using combinatorial proofs:

1. For any natural numbers \(r\), \(n\), with \(1 ≤ r ≤ n\), \(\binom{n}{r} = \binom{n−1}{r−1} + \binom{n−1}{r}\). [Hint: Consider the number of ways to form a team of \(r\) people from a group of \(n\) people. Then break the problem into two cases depending on whether or not one specific person is chosen for the team.]
2. For any natural numbers \(k\), \(r\), \(n\), with \(0 ≤ k ≤ r ≤ n\), \(\binom{n}{r} \binom{r}{k} = \binom{n}{k} \binom{n−k}{r−k}\). [Hint: Consider the number of ways to choose \(r\) dogs who will enter a competition, from a set of \(n\) dogs, and to choose \(k\) of those \(r\) dogs to become the finalists. Then choose the finalists first, followed by the other dogs who entered the competition.]
3. For any natural number \(n\), \(\sum_{r=0}^{n} \binom{n}{r}^2 = \binom{2n}{n}\).
4. For \(n ≥ 1\) and \(k ≥ 1\), \(\dfrac{n!}{(n−k)!} = n \dfrac{(n−1)!}{(n−1−(k−1))!}\).
5. For \(n ≥ 1\), \(3^n = \sum_{k=0}^{n} \binom{n}{k} 2^{n-k} \)

Exercise \(\PageIndex{3}\)

Sometimes the hardest part of a combinatorial proof can be figuring out what problem the given formula provides a solution to. For each of the following formulas, state a counting problem that can be solved by the formula.

1. \(n2^{n−1}\).
2. \(\sum_{r=0}^{n} r \binom{n}{r}\).
3. \(\sum_{k=r}^{n} \binom{n}{k} \binom{k}{r}\).
4. \(2^{n−r} \binom{n}{r} \).