Double-counting, Part 1

Double-counting is one of my favorite proof techniques. The idea is simple: count the same thing in two different ways. In this post, I’ll give some examples of double-counting in the context of proving identities involving binomial coefficients, but it’s a very general technique that can be applied to many other types of problems.

Pascal’s identity. The following is known as Pascal’s identity:

{n \choose k} = {n-1 \choose k-1} + {n-1 \choose k}

Of course, Pascal’s Identity can also be proven directly using simple algebra, but there is a nice double-counting alternative. Suppose we have a group of $n$ people, and we’d like to choose a committee of $k$ members. There are $n \choose k$ ways of doing this. Now let’s count the number of committees in a different way. Suppose we pick out one particular person from the group, let’s call her Alice. There are $n-1\choose k-1$ committees that include Alice, because after we’ve included Alice, there are $k-1$ remaining committee members to choose out $n-1$ remaining people. Similarly, there are $n-1\choose k$ committees that exclude Alice, because all $k$ committee members must be chosen out of the remaining $n-1$ people. The total number of committees is equal to the number of committees that include Alice plus the number of committees that exclude Alice, and this completes the proof of Pascal’s Identity.

Binomial theorem. Here is another familiar identity:

{n \choose 0} + {n \choose 1} + \dots + {n \choose n} = 2^n

This identity can be directly obtained by applying the Binomial Theorem to $(1+1)^n$. But once again, we can use a double-counting argument. Suppose we have a group of $n$ people. Let’s count the total number of subsets of this group. One way to count is to realize that there are $n \choose k$ different subsets of size $k$. So the total number of subsets of any size is the sum on the left-hand side of the identity. On the other hand, we can count subsets by looking at each person one at a time. Each person can either be included or excluded in the subset ($2$ possibilities), which yields a total of $2\times 2 \times \dots \times 2 = 2^n$ possible subsets.

Binomial products. This example involves products:

{n \choose s}{s \choose r} = {n \choose r}{n-r \choose s-r}

Consider a group of $n$ people. This time, we count the number of ways of selecting a team of $s$ members, among which $r$ are designated as captains. One way to do this is to start by selecting the team, which can be done in $n \choose s$ ways. For each team, we then select the captains, which can be done in $s \choose r$ ways. The total is therefore ${n \choose s}{s \choose r}$. Another way to count is to start by selecting the captains first, which can be done in $n \choose r$ ways. Then, we must select the rest of the team. There remains $n-r$ people and we must choose $s-r$ to round out the team. So the total count is ${n \choose r}{n-r \choose s-r}$.

This technique of committee selection is very powerful. See if you can figure out how to apply it to the following example!

{n \choose 1} + 2 {n\choose 2} + 3 {n\choose 3} + \dots + n {n \choose n} = n 2^{n-1}

[Show Solution]

For more double-counting problems, check out Part 2!

3 thoughts on “Double-counting, Part 1”

  1. Random thought: I’m uncomfortable with the term “double counting” as the name of this technique, because it more often denotes something we don’t want to do[*] when trying to count configurations. In fact, the term is used in exactly this (negative) way in the solution of the elevator buttons problem on this blog. Maybe we should call it “independent counting” or something.

    [*] Well, usually we don’t want to do it. The Inclusion-Exclusion formula could be considered a method of very tightly controlled double counting.

    1. I agree that it’s an unfortunate name due to its double meaning (ha!). It’s also called “counting in two ways”, which is more literal but not as catchy. For what it’s worth, the wiki article calls it double counting.

Leave a Reply

Your email address will not be published. Required fields are marked *