## Baseball division champs

Today’s post is a Riddler problem about baseball, and it goes like this:

Assume you have a sport (let’s call it “baseball”) in which each team plays 162 games in a season. Assume you have a division of five teams (call it the “AL East”) where each team is of exact equal ability. Specifically, each team has a 50 percent chance of winning each game. What is the expected value of the number of wins for the team that finishes in first place?

The problem statement is a bit vague, so we must make some assumptions in order to solve the problem. Our first solution assumes that the win-loss records of the teams are mutually independent.
[Show Solution]

This next solution explains how to tackle the more realistic case where the games are not played independently, and explains why the independence assumption is a good one for the AL East.
[Show Solution]

## 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!