Skip to main content

Section 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.”

Definition 4.2.2.

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\text{;}\) and then we count the solutions to the same problem in a different way and obtain the answer \(g(n)\) for some function \(g\text{.}\) This is a combinatorial proof of the identity \(f(n)=g(n)\text{.}\)

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\text{,}\) but the same ideas hold if \(f\) and \(g\) are functions of more than one variable. Some of our examples will demonstrate this.

These ideas give us a methodical way to approach the proof of a combinatorial identity.

Combinatorial Proof outline

  1. Identify the problem you are counting. The first step is to identify a problem for which we will be counting the solutions. Sometimes the problem may be provided directly in the question. If so, this first step is easy. If that didn't happen, examine one or the other of the formulas you have been asked to show are equal, and come up with any problem whose solutions can be counted by that formula. Explain this problem, and state that you will be counting the solutions in two ways.

  2. Counting method 1. Explain why the left-hand side of the combinatorial identity counts the solutions to the problem you have identified. This is often easy, and perhaps even follows directly from definitions, especially if you came up with the problem yourself from that formula.

  3. Counting method 2. Explain why the right-hand side of the combinatorial identity counts the solutions to the problem you have identified. Unless it was challenging to identify a problem in the first place (which can certainly happen), this is likely to be the most challenging part of the proof.

  4. Conclusion. Note that since your methods both count the number of solutions to the same problem, the results must be equal, and state the identity that you have proven.

It is not always necessary to explicitly list and label each of these steps, but you may find it helpful as a method of clearly laying out your proof, and ensuring that it is correct and complete. Sometimes it may make sense to start with the right-hand side of the identity and then look at the left-hand side; this is perfectly acceptable.

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

\begin{equation*} \binom{n}{r}=\binom{n}{n-r}\text{.} \end{equation*}
Combinatorial proof.

The problem. We will count the number of ways of choosing \(r\) objects from a set of \(n\) distinct objects in two ways.

Counting method 1: By the definition of \(\binom{n}{r}\text{,}\) this is the number of ways of choosing \(r\) objects from a set of \(n\) distinct objects.

Counting method 2: Any time we choose \(r\) objects from a set of \(n\) 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.

Conclusion. Since both of these methods count the number of solutions to the same problem, it must be the case that for every natural number \(n\) and every integer \(r\) between \(0\) and \(n\text{,}\) we have

\begin{equation*} \binom{n}{r}=\binom{n}{n-r}\text{,} \end{equation*}

as desired.

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

\begin{equation*} \binom{n}{n-r}=\frac{n!}{(n-r)!(n-(n-r))!}=\frac{n!}{(n-r)!r!}=\binom{n}{r}\text{.} \end{equation*}

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.

When you are asked to prove a result using a combinatorial proof, it is important that you use this technique (including all of the steps explained above). In some cases, there are other proofs that you may find much easier (such as taking a special case of the Binomial Theorem). However, the goal of these exercises is not for you to show that you can come up with a correct proof, but to give you practice and experience in using a proof technique that you haven't seen before. Using a different proof technique completely defeats the purpose.

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 \(2^n\text{.}\) If we actually carry through on the first idea, this leads to another combinatorial identity (one that we already observed via the Binomial Theorem):

Prove that for every natural number \(n\text{,}\)

\begin{equation*} \sum_{r=0}^n \binom{n}{r}=2^n\text{.} \end{equation*}
Combinatorial proof.

The problem. We will count the number of subsets of an \(n\)-element set in two ways.

Counting method 1: For this example, we will start with the right-hand side of the identity. We have seen in Example 4.1.1 that the number of subsets of a set of \(n\) elements is \(2^n\text{.}\)

Counting method 2: 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\text{.}\) 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}\text{.}\) Thus, the total number of subsets of our original set must be \(\sum_{r=0}^n\binom{n}{r}\text{.}\)

Conclusion. 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,

\begin{equation*} \sum_{r=0}^n \binom{n}{r}=2^n\text{,} \end{equation*}

as desired.

This was in fact the idea that was used by Sushruta (c.800BCE—c.700BCE) in his flavour calculations. It has also been used in a variety of other contexts over the years. The Indian poet Halayudha (10th century CE) considered the number of kinds of poetic meter that were possible in a line with a fixed number of syllables, where the meter determined which syllables were short and which were long. If the line has \(k\) syllables, then the number of choices is \(2^k\text{,}\) and he used combinations in his calculations. Bhāskara II (1114—1185), who we earlier saw also used permutations, asked in the same book about the number of ways of choosing some collection of doors to be open in a palace with \(8\) doors (requiring that at least one be open), and arrived at the answer \(2^8-1=255\text{.}\) Although it is an application of this particular combinatorial proof rather than an example of a combinatorial proof, we provide one other historical example in slightly more detail.

Abū-l'Abbās Ahmad ibn al-Bannā' (1256—1321) of Morocco considered a triangle to have \(5\) key associated values that might be of interest: the lengths of the three sides; the height; and the area. He asked how many geometrical problems associated with triangles could be posed, in which some number (at least one, but not all) of these quantities are provided and the rest are asked for. (Whether or not the problem is solvable from the given information is not relevant.) He also asked similar questions about circles (to which he attributed three associated values: diameter, perimeter, and area), and other shapes, but we'll only do the calculation for triangles.

Solution

Any subset of the five quantities can be provided, except at least one value must be provided (so the subset cannot be empty) and the problem cannot provide all of the values (so the subset cannot be the entire set). The answer is therefore \(2^5-\binom{5}{0}-\binom{5}{5}=32-2=30\text{.}\)

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

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

The problem. On this occasion the problem was given to us explicitly, and we will need to come up with the two sides of the combinatorial identity. We will find two methods for counting the number of ways of including at least one woman in an \(r\)-member focus group, from an initial collection of \(n\) men and \(n\) women.

Counting method 1: 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}\text{.}\)

Counting method 2: 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\le i \le 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

\begin{equation*} \sum_{i=1}^r\binom{n}{i}\binom{n}{r-i}\text{.} \end{equation*}

Conclusion. Since both of these methods counted solutions to the same problem, this argument yields the combinatorial identity

\begin{equation*} \sum_{i=1}^r\binom{n}{i}\binom{n}{r-i}=\binom{2n}{r}-\binom{n}{r}\text{,} \end{equation*}

which we have thereby proven.

Our next combinatorial identity was used historically to work out unknown binomial coefficients from known values.

Although his ultimate goal was to compute how many “words” (letter combinations of various lengths) could be composed from the Arabic alphabet of \(28\) letters, Ahmad ibn Mun'im al-'Abdarī (11??—1228) began with a different problem.

In Morocco around \(1200\)CE, where Ahmad lived, silk tassels made with a variety of colours of silk threads were a common decoration. He asked: of the \(10\) available colours, how many ways are there to make tassels that contain exactly three colours? (Since the threads are wound together and get disarranged easily, the order of the colours is not relevant.)

Solution

It was known to Ahmad how to calculate \(\binom{n}{2}\) for any \(n\text{,}\) but explicit formulas for \(\binom{n}{3}\) were not known. He began by ordering the colours:

  1. indigo;
  2. black;
  3. emerald;
  4. silver;
  5. orange;
  6. white;
  7. azure;
  8. red;
  9. purple;
  10. gold.

Now he argued: the problem of choosing three colours can be broken down into \(8\) cases, depending on the highest numbered colour that is used. (This number must be at least \(3\) in order to allow two colours with smaller numbers to exist, and cannot be more than \(10\text{.}\)) For each choice of highest-numbered colour, he could work out the number of ways to choose the other two colours from colours with lower numbers as follows:

  1. you can choose colour \(3\) (emerald) as the highest colour; in this case you must choose two (both) of the colours with lower numbers (indigo and black). There are \(\binom{2}{2}=1\) ways to do this;
  2. you can choose colour \(4\) (silver) as the highest colour; in this case you must choose two of the three colours with lower numbers. There are \(\binom{3}{2}=3\) ways to do this;
  3. you can choose colour \(5\) (orange) as the highest colour; in this case you must choose two of the four colours with lower numbers. There are \(\binom{4}{2}=6\) ways to do this;
  4. you can choose colour \(6\) (white) as the highest colour; in this case you must choose two of the five colours with lower numbers. There are \(\binom{5}{2}=10\) ways to do this;
  5. you can choose colour \(7\) (azure) as the highest colour; in this case you must choose two of the six colours with lower numbers. There are \(\binom{6}{2}=15\) ways to do this;
  6. you can choose colour \(8\) (red) as the highest colour; in this case you must choose two of the seven colours with lower numbers. There are \(\binom{7}{2}=21\) ways to do this;
  7. you can choose colour \(9\) (purple) as the highest colour; in this case you must choose two of the eight colours with lower numbers. There are \(\binom{8}{2}=28\) ways to do this;
  8. you can choose colour \(10\) (gold) as the highest colour; in this case you must choose two of the nine colours with lower numbers. There are \(\binom{9}{2}=36\) ways to do this.

So in total, there are

\begin{equation*} 1+3+6+10+15+21+28+36=120 \end{equation*}

ways to create tassels with three colours. Notice that using our formula,

\begin{equation*} \binom{10}{3}=\frac{10\cdot 9 \cdot 8}{6}=120 \end{equation*}

also.

The argument used by Ahmad was also used by Abraham ibn Ezra (c. 1093—1167) in his study of planetary conjunctions (see Example 3.2.8). However, Ahmad observed this as a general pattern. We leave up to you to generalise this argument into a formal proof of the combinatorial identity that underlies it: that

\begin{equation*} \binom{n}{k}=\sum_{r=k-1}^{n-1}\binom{r}{k-1}. \end{equation*}

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\text{,}\) we may wish to count all of the ordered pairs \((x,y)\text{,}\) where \(x\in X\) and \(y\in Y\text{,}\) such that \((x,y)\) has some property. We can do this by first considering every possible value of \(x \in X\text{,}\) and for each such value, counting the number of \(y \in Y\) such that \((x,y)\) satisfies the desired property, or by first considering every possible value of \(y \in Y\text{,}\) and for each such value, counting the number of \(x \in 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\text{,}\) and counting pairs \((x,y)\) for which the element \(x\) appears in the subset \(y\text{.}\) By counting these pairs in two ways, we will find a combinatorial identity.

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 \in S\) and \(b \in B\) such that the street segment \(s\) is adjacent to the block \(b\) in two ways. Use this to deduce a combinatorial inequality.

Solution

Note that since the question asks us to deduce an inequality rather than an equality, one of our counts will not be precise. In other words, for one of our two counting methods, we will be trying to say that the result is at most or at least some formula, rather than that it is equal to that formula.

The problem. We will count the number of pairs \((s,b)\) with \(s \in S\) and \(b \in B\) such that the street segment \(s\) is adjacent to the block \(b\) in two ways.

Counting method 1: Let \(|S|=t\text{.}\) 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\text{,}\) there are two pairs \((s,b)\) such that \(s\) is adjacent to the block \(b\text{.}\) Multiplying this count by \(t\) (the number of street segments) tells us that the total number of pairs \((s,b)\in S\times B\) with \(s\) adjacent to \(b\) is \(2t\text{.}\)

Counting method 2: Let \(|B|=c\text{.}\) Each block is adjacent to at least 3 street segments (this is where the inequality arises): 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\text{.}\) Multiplying this count by \(c\) (the number of blocks) tells us that the total number of pairs \((s,b)\in S\times B\) with \(s\) adjacent to \(b\) is at least \(3c\text{.}\)

Conclusion. We deduce that \(2t \ge 3c\text{.}\)

Let \(P\) be the set of people in a group, with \(|P|=p\text{.}\) Let \(C\) be a set of clubs formed by the people in this group, with \(|C|=c\text{.}\) 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)\in P\times C\) such that person \(b\) is in club \(h\text{,}\) and deduce a combinatorial identity.

Prove the following combinatorial identities, using combinatorial proofs:

  1. For any natural numbers \(r, n\text{,}\) with \(1 \le r \le n\text{,}\) \(\binom{n}{r}=\binom{n-1}{r-1}+\binom{n-1}{r}\text{.}\)
    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\text{,}\) with \(0 \le k \le r \le n\text{,}\) \(\binom{n}{r}\binom{r}{k}=\binom{n}{k}\binom{n-k}{r-k}\text{.}\)
    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\text{,}\) \(\sum_{r=0}^n\binom{n}{r}^2=\binom{2n}{n}\text{.}\)

  4. For \(n \ge 1\) and \(k \ge 1\text{,}\) \(\frac{n!}{(n-k)!}=n\frac{(n-1)!}{(n-1-(k-1))!}\text{.}\)

  5. For \(n \ge 1\text{,}\) \(3^n=\sum_{k=0}^n \binom{n}{k}2^{n-k}\text{.}\)

Sometimes the hardest part of a combinatorial proof can be the first step: 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}\text{.}\)

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

  3. \(\sum_{k=r}^n\binom{n}{k}\binom{k}{r}\text{.}\)

  4. \(2^{n-r}\binom{n}{r}\text{.}\)