maths.free › Combinatorics & Graph Theory › 4. Counting › Combinatorial Proofs

Combinatorial Proofs

Investigation Look at any cell in the interior Pascal's triangle and the six numbers that surround it.

Combinatorial Proofs

Combinatorial arguments are among the most beautiful in all of mathematics. Oftentimes, statements that can be proved by other, more complicated methods (usually involving large amounts of tedious algebraic manipulations) have very short proofs once you can make a connection to counting. In this section, we introduce a new way of thinking about combinatorial problems with several examples. Our goal is to help you develop a gut feeling for combinatorial problems.

Example

Let \(n\) be a positive integer. Use to explain why \[\begin{aligned}\end{aligned}\]

Solution

Consider an \((n+1)\times (n+1)\) array of dots as depicted in . There are \((n+1)^2\) dots altogether, with exactly \(n+1\) on the main diagonal. The off-diagonal entries split naturally into two equal size parts, those above and those below the diagonal.

Furthermore, each of those two parts has \(S(n)=1+2+3+\dots+n\) dots. It follows that \[\begin{aligned}\end{aligned}\] and this is obvious! Now a little algebra on the right hand side of this expression produces the formula given earlier.

Example

Let \(n\) be a positive integer. Explain why \[\begin{aligned}\end{aligned}\]

Solution

The left hand side is just the sum of the first \(n\) odd integers. But as suggested in , this is clearly equal to \(n^2\).

Example

Let \(n\) be a positive integer. Explain why \[\begin{aligned}\end{aligned}\]

Solution

Both sides count the number of bit strings of length \(n\), with the left side first grouping them according to the number of \(0\)'s.

Example

Let \(n\) and \(k\) be integers with \(0\le k\lt n\). Explain why \[\begin{aligned}\end{aligned}\]

Solution

To prove this formula, we simply observe that both sides count the number of bit strings of length\(n\) that contain \(k+1\) \(1\)'s with the right hand side first partitioning them according to the last occurence of a\(1\). (For example, if the last \(1\) occurs in position \(k+5\), then the remaining \(k\) \(1\)'s must appear in the preceding \(k+4\) positions, giving \(C(k+4,k)\) strings of this type.) Note that when \(k=1\) (so \(k+1=2\)), we have the same formula as developed earlier for the sum of the first \(n\) positive integers.

Condensed — the full section is in Keller & Trotter, Applied Combinatorics.

Section Preview

Investigation

Look at any cell in the interior Pascal's triangle and the six numbers that surround it. For example, you might look at this cell:

Of the six numbers surrounding our selected cell, we will divide them into two groups of three, alternating between the groups. So for this example, we have a group with 4, 10, and 15, and a second group with 5, 6, and 20. But notice: \[4\cdot 10 \cdot 15 = 600 = 5\cdot 6 \cdot 20\]. Does this work no matter what center cell you pick? Why??

One of the coolest things about combinatorics is that you can often answer the same counting question in dramatically different ways. When we recognize this about a particular problem, we can often generalize the question to reveal two different expressions that must represent the same quantity. The counting problem itself becomes a proof of the equality of the two expressions. This style of proof is called a combinatorial proof.

Patterns in Pascal's Triangle

Have a look again at Pascal's triangle. Forget for a moment where it comes from. Just look at it as a mathematical object. What do you notice?

There are lots of patterns hidden away in the triangle, enough to fill a reasonably sized book. Here are just a few of the most obvious ones:

The entries on the border of the triangle are all 1.
Any entry not on the border is the sum of the two entries above it.
The triangle is symmetric. In any row, entries on the left side are mirrored on the right side.
The sum of all entries on a given row is a power of 2. (You should check this!)

We would like to state these observations in a more precise way, and then prove that they are correct. Now each entry in Pascal's triangle is in fact a binomial coefficient. The 1 on the very top of the triangle is \(\binom{0}{0}\). The next row (which we will call row 1, even though it is not the top-most row) consists of \(\binom{1}{0}\) and \(\binom{1}{1}\). Row 4 (the row 1, 4, 6, 4, 1) consists of the binomial coefficients \[\binom{4}{0} ~~ \binom{4}{1} ~~ \binom{4}{2} ~~ \binom{4}{3} ~~ \binom{4}{4}\].

Given this description of the elements in Pascal's triangle, we can rewrite the above observations as follows:

\(\binom{n}{0} = 1\)\(\binom{n}{n} = 1\)
\(\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}\)
\(\binom{n}{k} = \binom{n}{n-k}\)
\(\binom{n}{0} + \binom{n}{1} + \binom{n}{2} + \cdots + \binom{n}{n} = 2^n\)

Each of these is an example of a binomial identity : an identity (i.e., equation) involving binomial coefficients.

Our goal is to establish these identities. We wish to prove that they hold for all values of \(n\) and \(k\). These proofs can be done in many ways. One option would be to give algebraic proofs, using the formula for \(\binom{n}{k}\): \[\binom{n}{k} = \frac{n!}{(n-k)!\,k!}\].

Here's how you might do that for the second identity above.

This is certainly a valid proof but also is entirely useless. Even if you understand the proof perfectly, it does not tell you why the identity is true. A better approach would be to explain what \(\binom{n}{k}\) means and then say why that is also what \(\binom{n-1}{k-1} + \binom{n-1}{k}\) means. Let's see how this works for the four identities we observed above.

Condensed — the full section is in Levin, Discrete Mathematics: An Open Introduction.

More Proofs

The explanatory proofs given in the above examples are typically called combinatorial proofs. In general, to give a combinatorial proof for a binomial identity, say \(A = B\), you do the following:

Find a counting problem you will be able to answer in two ways.
Explain why one answer to the counting problem is \(A\).
Explain why the other answer to the counting problem is \(B\).

Since both \(A\) and \(B\) are the answers to the same question, we must have \(A = B\).

The tricky thing is coming up with the question. This is not always obvious, but it gets easier the more counting problems you solve. You will start to recognize types of answers as the answers to types of questions. More often what will happen is that you will be solving a counting problem and happen to think up two different ways of finding the answer. Now you have a binomial identity, and the proof is right there. The proof is the problem you just solved together with your two solutions.

For example, consider this counting question:

How many 10-letter words use exactly four A's, three B's, two C's, and one D?

Let's try to solve this problem. We have 10 spots for letters to go. Four of those need to be A's. We can pick the four A-spots in \(\binom{10}{4}\) ways. Now where can we put the B's? Well there are only 6 spots left; we need to pick \(3\) of them. This can be done in \(\binom{6}{3}\) ways. The two C's need to go in two of the 3 remaining spots, so we have \(\binom{3}{2}\) ways of doing that. That leaves just one spot of the D, but we could write that 1 choice as \(\binom{1}{1}\). Thus the answer is: \[\binom{10}{4}\binom{6}{3}\binom{3}{2}\binom{1}{1}\].

But why stop there? We can find the answer another way too. First let's decide where to put the one D: we have 10 spots and we need to choose 1 of them, so this can be done in \(\binom{10}{1}\) ways. Next, choose one of the \(\binom{9}{2}\) ways to place the two C's. We now have \(7\) spots left, and three of them need to be filled with B's. There are \(\binom{7}{3}\) ways to do this. Finally the A's can be placed in \(\binom{4}{4}\) (that is, only one) ways. So another answer to the question is \[\binom{10}{1}\binom{9}{2}\binom{7}{3}\binom{4}{4}\].

Interesting. This gives us the binomial identity: \[\binom{10}{4}\binom{6}{3}\binom{3}{2}\binom{1}{1} = \binom{10}{1}\binom{9}{2}\binom{7}{3}\binom{4}{4}\].

Condensed — the full section is in Levin, Discrete Mathematics: An Open Introduction.

Practice (23)

Try each one on paper first. Reveal the answer to check; verified ones can be opened in the solver for every step.

Consider the illustration below. Although the grid of circles is eight by seven, please treat it as if it had \(n+1\) rows and \(n\) columns. Explain how this illustration gives another way to arrive at the formula \[\begin{aligned}\end{aligned}\] from .
Explain how the identity \(C(n,k) = C(n,n-k)\) is used in .
Which of the following describes the overall strategy for a combinatorial proof?
Write a counting question that you could use to establish the identity: \[\binom{x+y}{x} = \binom{x+y}{y}\].
What questions do you have after reading this section? Write at least one question about the content of this section that you are curious about.
Create a combinatorial proof of the identity \(10+10 = 2\cdot 10\).
If you were asked to give a combinatorial proof of the identity \(\binom{n}{2}\binom{n-2}{k} = \binom{n}{k}\binom{n-k}{2}\), which of the following would be reasonable questions to use?
Give a combinatorial proof of the identity \(2+2+2 = 3\cdot 2\).

Reveal the answer

Proof
Question: How many 2-letter words start with a, b, or c and end with either y or z?
Answer 1: There are two words that start with a, two that start with b, two that start with c, for a total of \(2+2+2\).
Answer 2: There are three choices for the first letter and two choices for the second letter, for a total of \(3 \cdot 2\).
Since the two answers are both answers to the same question, they are equal. Thus \(2 + 2 + 2 = 3\cdot 2\).
Suppose you own \(x\) fezzes and \(y\) bow ties. Of course, \(x\) and \(y\) are both greater than 1.
1. How many combinations of fez and bow tie can you make? You can wear only one fez and one bow tie at a time. Explain.
2. Explain why the answer is also \({x+y \choose 2} - {x \choose 2} - {y \choose 2}\). (If this is what you claimed the answer was in part (a), try it again.)
3. Use your answers to parts (a) and (b) to give a combinatorial proof of the identity \[{x+y \choose 2} - {x \choose 2} - {y \choose 2} = xy\].
How many triangles can you draw using the dots below as vertices?
1. Find an expression for the answer which is the sum of three terms involving binomial coefficients.
2. Find an expression for the answer which is the difference of two binomial coefficients.
3. Generalize the above to state and prove a binomial identity using a combinatorial proof. Say you have \(x\) points on the horizontal axis and \(y\) points in the semi-circle.
Reveal the answer
Hint:
There will be 185 triangles. But to find them
1. How many vertices of the triangle can be on the horizontal axis?
2. Will any three dots work as the vertices?
Consider all the triangles you can create using the points shown below as vertices. Note that we are not allowing degenerate triangles (ones with all three vertices on the same line), but we do allow non-right triangles.
1. Find the number of triangles, and explain why your answer is correct.
2. Find the number of triangles again, using a different method. Explain why your new method works.
3. State a binomial identity that your two answers above establish (that is, give the binomial identity that your two answers are a proof for). Then generalize this using \(m\)'s and \(n\)'s.
Reveal the answer

Hint:
The answer is 120.
A woman is getting married. She has 15 best friends but can only select 6 of them to be her bridesmaids, one of which needs to be her maid of honor. How many ways can she do this?
1. What if she first selects the 6 bridesmaids, and then selects one of them to be the maid of honor?
2. What if she first selects her maid of honor, and then 5 other bridesmaids?
3. Explain why \(6 {15 \choose 6} = 15 {14 \choose 5}\).
Reveal the answer
1. She has \({15 \choose 6}\) ways to select the 6 bridesmaids, and then for each way, has 6 choices for the maid of honor. Thus she has \({15 \choose 6}6\) choices.
2. She has 15 choices for who will be her maid of honor. Then she needs to select 5 of the remaining 14 friends to be bridesmaids, which she can do in \({14 \choose 5}\) ways. Thus she has \(15 {14 \choose 5}\) choices.
3. We have answered the question (how many wedding parties can the bride choose from) in two ways. The first way gives the left-hand side of the identity, and the second way gives the right-hand side of the identity. Therefore the identity holds.
Consider the identity: \[k{n\choose k} = n{n-1 \choose k-1}\].
1. Is this true? Try it for a few values of \(n\) and \(k\).
2. Use the formula for \({n \choose k}\) to give an algebraic proof of the identity.
3. Give a combinatorial proof of the identity.
Reveal the answer

Hint:
Try .
Give a combinatorial proof of the identity \({n \choose 2}{n-2 \choose k-2} = {n\choose k}{k \choose 2}\).

Reveal the answer

Hint:
What if you wanted a pair of co-maids-of-honor?
Proof
Question: You have a large container filled with ping-pong balls, all with a different number on them. You must select \(k\) of the balls, putting two of them in a jar and the others in a box. How many ways can you do this?
Answer 1: First select 2 of the \(n\) balls to put in the jar. Then select \(k-2\) of the remaining \(n-2\) balls to put in the box. The first task can be completed in \({n \choose 2}\) different ways and the second task in \({n-2 \choose k-2}\) ways. Thus there are \({n \choose 2}{n-2 \choose k-2}\) ways to select the balls.
Answer 2: First select \(k\) balls from the \(n\) in the container. Then pick 2 of the \(k\) balls you picked to put in the jar, placing the remaining \(k-2\) in the box. The first task can be completed in \({n \choose k}\) ways and the second task in \({k \choose 2}\) ways. Thus there are \({n \choose k}{k \choose 2}\) ways to select the balls.
Since both answers count the same thing, they must be equal, and the identity is established.
Consider the binomial identity \[\binom{n}{1} + 2 \binom{n}{2} + 3 \binom{n}{3} + \cdots + n\binom{n}{n} = n2^{n-1}\].
1. Give a combinatorial proof of this identity. Hint: What if some number of a group of \(n\) people wanted to go to an escape room, and among those going, one needed to be the team captain?
2. Give an alternate proof by multiplying out \((1+x)^n\) and taking derivatives of both sides.
Reveal the answer

Hint:
For the combinatorial proof: What if you don't yet know how many bridesmaids you will have?
Give a combinatorial proof for the identity \(1 + 2 + 3 + \cdots + n = {n+1 \choose 2}\).

Reveal the answer

Hint:
Count handshakes.
Consider the bit strings in \(\B^6_2\) (bit strings of length 6 and weight 2).
1. How many of those bit strings start with 1?
2. How many of those bit strings start with 01?
3. How many of those bit strings start with 001?
4. Are there any other strings we have not counted yet? Which ones, and how many are there?
5. How many bit strings are there total in \(\B^6_2\)?
6. What binomial identity have you just given a combinatorial proof for?
Let's count ternary digit strings, that is, strings in which each digit can be 0, 1, or 2.
1. How many ternary digit strings contain exactly \(n\) digits?
2. How many ternary digit strings contain exactly \(n\) digits and \(n\) 2's.
3. How many ternary digit strings contain exactly \(n\) digits and \(n-1\) 2's. (Hint: Where can you put the non-2 digit, and then what could it be?)
4. How many ternary digit strings contain exactly \(n\) digits and \(n-2\) 2's. (Hint: See previous hint.)
5. How many ternary digit strings contain exactly \(n\) digits and \(n-k\) 2's.
6. How many ternary digit strings contain exactly \(n\) digits and no 2's. (Hint: What kind of a string is this?)
7. Use the above parts to give a combinatorial proof for the identity \[{n \choose 0} + 2{n \choose 1} + 2^2{n \choose 2} + 2^3{n \choose 3} + \cdots + 2^n{n \choose n} = 3^n\].
How many ways are there to rearrange the letters in the word rearrange? Answer this question in at least two different ways to establish a binomial identity.
Establish the identity below using a combinatorial proof. \[{2 \choose 2}{n \choose 2} + {3 \choose 2}{n-1 \choose 2} + {4\choose 2}{n-2 \choose 2} + \cdots + {n\choose 2}{2\choose 2} = {n+3 \choose 5}\].

Reveal the answer

Hint:
This one might remind you of
In we established that the sum of any row in Pascal's triangle is a power of two. Specifically, \[{n\choose 0} + {n \choose 1} + {n\choose 2} + \cdots + {n \choose n} = 2^n\]. The argument given there used the counting question, How many pizzas can you build using any number of \(n\) different toppings? To practice, give new proofs of this identity using different questions.
1. Use a question about counting subsets.
2. Use a question about counting bit strings.
3. Use a question about counting lattice paths.
Reveal the answer

Hint:
For the lattice paths, think about what sort of paths \(2^n\) would count. Not all the paths will end at the same point, but you could describe the set of end points as a line.
1. The Stanley Cup is decided in a best of 7 tournament between two teams. In how many ways can your team win? Let's answer this question two ways:
  1. How many of the 7 games does your team need to win? How many ways can this happen?
  2. What if the tournament goes all 7 games? So you win the last game. How many ways can the first 6 games go down?
  3. What if the tournament goes just 6 games? How many ways can this happen? What about 5 games? 4 games?
  4. What are the two different ways to compute the number of ways your team can win? Write down an equation involving binomial coefficients (that is, \({n \choose k}\)'s). What pattern in Pascal's triangle is this an example of?
2. Generalize. What if the rules changed, and you played a best of \(9\) tournament (5 wins required)? What if you played an \(n\) game tournament with \(k\) wins required to be named champion?
Let \(k_1, k_2, \ldots, k_j\) be a list of positive integers that sum to \(n\) (i.e., \(\sum_{i=1}^j k_i = n\)). Use two graphs containing \(n\) vertices to explain why \[\sum_{i = 1}^j \binom{k_i}{2} \le \binom{n}{2}\].

Reveal the answer

Hint:
How many edges does \(K_n\) have? One of the two graphs will not be connected (unless \(j=1\) ).

Symbols used here

\binom{n}{k}

binomial coefficient, "n choose k"
Number of k-element subsets of n things: n!/(k!(n−k)!).

imaginary unit
i² = −1.

\leq,\ \geq

less/greater than or equal
Inequalities that allow equality; < and > exclude it.

factorial
n × (n−1) × … × 1; the number of orderings of n things. 0! = 1.

\sum_{k=1}^{n} a_k

summation
Add a_k for k = 1 up to n.

\prod_{k=1}^{n} a_k

product
Multiply a_k for k = 1 up to n.

\emptyset,\ |A|

empty set, cardinality
The set with no elements; the number of elements of A.

How to: Combinatorial Proofs

Write counting problems that have a given answer.
Write two different solutions to a counting problem.
Prove binomial identities using combinatorial proofs.

Questions people ask

Permutation or combination?

Ask whether order matters. A lock code is a permutation (order matters); a hand of cards is a combination (it does not).

What is a graph in this sense?

Dots (vertices) joined by lines (edges) — not a plot. Road maps, social networks and molecules are graphs; questions like "is there a route" and "how few colours" are graph theory.

Try your own

Parts of this page are adapted from Keller & Trotter, Applied Combinatorics (CC BY-SA 4.0), Levin, Discrete Mathematics: An Open Introduction (CC BY-SA 4.0). Condensed and re-explained here; errors are ours.

More in Combinatorics & Graph Theory

The counting principles Pigeonhole principle and inclusion–exclusion Binomial coefficients and Pascal's triangle Recurrences and generating functions Graphs: vertices, edges, degrees Paths, cycles, trees, Euler and Hamilton Colouring and planar graphs