Double-counting, Part 2

This post is a follow-up to Part 1, where I talked about the technique of double-counting in the context of proving combinatorial identities. In this post, I’ll show three more identities that can be proven using simple double-counting. Test your skills!

First identity. This is Vandermonde’s Identity.
$\sum_{k=0}^p {m \choose k}{n \choose p-k} = {m+n \choose p}$

[Show Solution]

Second identity. This is the Christmas Stocking Identity. It is also sometimes called the Hockey-Stick Identity.
$\sum_{k=0}^m {n+k \choose n} = {m+n+1 \choose n+1}$

[Show Solution]

Third identity. This one looks similar to the first one, but notice that the upper coefficient is varying this time.
$\sum_{k=0}^p {k \choose m}{p-k \choose n} = {p+1 \choose m+n+1}$

[Show Solution]

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!

Monsters’ gems

Once again, The Riddler does not disappoint! This puzzle is about slaying monsters and collecting gems.

A video game requires you to slay monsters to collect gems. Every time you slay a monster, it drops one of three types of gems: a common gem, an uncommon gem or a rare gem. The probabilities of these gems being dropped are in the ratio of 3:2:1 — three common gems for every two uncommon gems for every one rare gem, on average. If you slay monsters until you have at least one of each of the three types of gems, how many of the most common gems will you end up with, on average?

Here is my solution:
[Show Solution]

A more brute-force approach:
[Show Solution]

Yet another solution approach with very nice write-up can be found on Andrew Mascioli’s blog

Overflowing martini glass

This Riddler puzzle is all about conic sections.

You’ve kicked your feet up and have drunk enough of your martini that, when the conical glass (🍸) is upright, the drink reaches some fraction p of the way up its side. When tipped down on one side, just to the point of overflowing, how far does the drink reach up the opposite side?

Here is my solution:
[Show Solution]

Counting parallelograms

The following problem appeared in the 1991 CMO, and it has a particularly clever solution.

In the figure, the side length of the large equilateral triangle is $3$ and $f(3)$, the number of parallelograms bounded by sides in the grid, is $15$. For the general analogous situation, find a formula for $f(n)$, the number of parallelograms, for a triangle of side length $n$.

[Show Solution]

Proud partygoers puzzle

Another great problem from the Riddler blog.

A group of N people are in attendance at your shindig, some of whom are friends with each other. (Let’s assume friendship is symmetric — if person A is friends with person B, then B is friends with A.) Suppose that everyone has at least one friend at the party, and that a person is “proud” if her number of friends is strictly larger than the average number of friends that her own friends have. (A competitive lot, your guests.)

Importantly, more than one person can be proud. How large can the share of proud people at the party be?

The solution:
[Show Solution]

A clever integral

I was recently reminded of this problem from one of my favorite books: Problem-Solving Through Problems. The problem originally appeared in the 1980 Putnam Competition.

Evaluate the following definite integral.

$\int_0^{\pi/2} \frac{\mathrm{d}x}{1 + (\tan x)^{\sqrt{2}}}$

The solution:
[Show Solution]

Elevator button puzzle

This problem was originally posted on the Riddler blog. Here it goes:

In a building’s lobby, some number (N) of people get on an elevator that goes to some number (M) of floors. There may be more people than floors, or more floors than people. Each person is equally likely to choose any floor, independently of one another. When a floor button is pushed, it will light up.

What is the expected number of lit buttons when the elevator begins its ascent?

My solution:
[Show Solution]

A much more elegant solution, courtesy of Ross Boczar
[Show Solution]