Combinatorial proofs: intro and overview

Combinatorics is an extremely broad field, applications of which appear all over the place. Some fields, like discrete probability and computer science, simply *could not even exist* without combinatorics. In putting together a single-semester combinatorics course, I wanted to have some kind of narrative throughout so that we weren't just talking about random selections of cute problems in the field. As a result, what we'll be focusing on is what is called "combinatorial proof," also known as "proof by two way counting," "counting proof," and a variety of other aliases.

The idea of a counting proof is that it counts something. This might sound silly, so here's an example of the difference between a combinatorial proof and a non-combinatorial proof of the same thing.

Binomial coefficients

You might have seen binomial coefficients before. They look like this: $${n \choose k}$$ (read "n choose k") and they represent the number of ways to choose k elements out of a set of n distinguishable elements. Whenever k > n, this coefficient is equal to zero. By convention, we set
$$ {0 \choose 0} = 1.$$ A nice, intuitive way to think about this is that we're choosing a committee of k students out of a class of n students. Often, binomial coefficients are defined in the following way: $${n \choose k} = \frac{n!}{k!(n-k)!},$$ where we use the notation m! to mean the product m(m-1)(m-2)...(2)(1) (note that by convention, we define 0! = 1). But this says nothing about committees of students like our first definition, so let's see if we can figure out why these things are the same. We'll look at a clunky induction style proof first, and then at a combinatorial proof.

Definition: For positive integers k and n, we define the binomial coefficient $${n \choose k}$$ to be the number of ways to choose a committee of k people out of a set of n people. If k > n, we define the binomial coefficient to equal 0. 

Claim: For all integers 1≤ k≤ n, we have $${n \choose k} = \frac{n!}{k!(n-k)!}.$$

Non-combinatorial proof of Claim 1: One way we can prove this is by induction on k. 

Base case: k=1. The number of ways to choose 1 person out of a group of n people is simply n. At the same time, $$\frac{n!}{1!(n-1)!}=\frac{n(n-1)(n-2) \dots 1}{1 (n-1)(n-2) \dots 1} = \frac{n}{1} = n,$$ so we have verified this claim to be true for k=1. 

Induction step: Suppose that the claim holds for all k<m, where m is any integer greater than 1 but not exceeding n. Now we'll use this to prove that it holds for k=m. The number of ways to form an m person committee out of a group of n people is nearly the same as the number of ways to form an m-1 person committee out of a group of n people, then pick one of the remaining n-(m-1) people to add into the committee. If we did this, though, we'd be over-counting. For example, when m=3: if we chose Alice and Bob out of the class, then chose Charles as our third committee member, we'd end up with the same committee as if we first chose Alice and Charles, and then added Bob as our third member. Therefore, we have to divide by m: the number of different orders in which a particular committee of m members can be chosen.

Now, by the product rule, we have: $$ {n \choose m} = {n \choose m{-}1}{n-(m-1) \choose 1}\frac{1}{m} = {n \choose m-1}(n-(m-1))\frac{1}{m}. $$ By the induction hypothesis (i.e. what we assumed at the start of the induction step), we know that 

$${n \choose m-1} = \frac{n!}{(m-1)!(n-(m-1))!}.$$

Combining this with what we realized above gives
$$\begin{array}{ll} {n \choose m} & =  {n \choose m-1}(n-(m-1)) \frac{1}{m}\\ & = \frac{n!}{(m-1)!(n-(m-1))!}\frac{n-(m-1)}{m}  \\ & = \frac{n!}{(m)!(n-(m-1)-1)!} \\ & =\frac{n!}{m!(n-m)!} \end{array}$$

as desired.  ▢ 

OK, great, I guess... we proved what we wanted to prove. So now we know it's true. However, we still have no idea why it's true! This is a perfect example of where a combinatorial proof of the same claim would actually give us more information (and be way simpler to follow, as well). Here goes: 

Combinatorial proof of Claim 1: Let's start this proof with a question: how many ways can the numbers 1 through n be arranged in a list? 

On the one hand, there are n! ways to arrange our numbers, since there are n choices for which number is first, n-1 for which is second, and so on. On the other hand, let's condition on which numbers appear in the first k places in our arrangement. There are 

$${n \choose k} $$

ways to pick k numbers out of the n to appear. Once they're chosen, there are k! ways to arrange them in a line. Similarly, there are (n-k)! ways to arrange the remaining n-k numbers in the line. Hence, by the product rule, the numbers 1 through n can be arranged in 

$${n \choose k}k!(n-k)! $$

ways. 

So we've now shown (by counting in two different ways) that 

$$ n! = {n \choose k}k!(n-k)!, $$

and therefore by dividing both sides by k!(n-k)! we have 

$${n \choose k} = \frac{n!}{k!(n-k)!},$$

as desired. ▢ 

This second proof was way shorter, required less fancy footwork* (like that dance we did in our induction step), and way less heavy machinery (like induction). And most importantly, we now have some understanding of *why* this identity is true, rather than just knowing that it's true. This is the beauty of proofs by two-way counting, and our goal this semester will be to use these kind of proofs to gain insights that are deeper and more intuitively apparent than we could with other proof techniques. We'll also be able to use these counting proofs to gain intuition in places where everything seems completely abstract, such as algebra, number theory, identities involving negative numbers, and so on. I'm excited, you're excited, it's gonna be a great semester!

* By the way, that fancy footwork was counting. So even when we set things up without counting in mind, we still needed to count in order to get through it.