Counting in two ways

One of the many reasons why I like the subject of combinatorics is that many problems in this area can be understood by someone with very little (or sometimes even zero) knowledge of the field.  The solutions to these problems can sometimes be likewise simple (but often beautiful and insightful) or extremely difficult (a classic example is the Four Color Theorem which until very recently was a conjecture that remained unsolved for several hundred years).  Here I will stick with problems of the first kind.

In this post I will present some formulas (or combinatorial identities) that can be explained by counting the same set of objects or quantities in two different ways.  Here is a simple example:
Let \( {n \choose k}\) be the number of ways that k objects can be chosen from a set of n objects (this is the familiar binomial coefficient).  We want to show that \[ {n\choose k} = {n-1 \choose k} + {n-1 \choose k-1}.\]  Of course one can write out the formula for \({n \choose k}\) using factorials and then algebraically manipulate the right hand side so that it matches the left hand side.  However, that will provide you with no intuition about what is actually going on.  Here is the combinatorial, and much more insightful, explanation.  As already mentioned, the left hand side counts the number of ways we can select k objects from a set of n objects.  We want to show that the right hand side counts the same things.  For a specific object (out of the n), every subset of k objects either contains it or does not (there is no third possibility!).  Now it is easy to see that there are \({n-1 \choose k}\) ways to choose k objects without picking our specific one and there are \({n-1 \choose k-1}\) to choose k objects if we want to include our specific one.  This explains the formula!

Here are a few more combinatorial identities that have similarly simple combinatorial interpretations:
\[\sum_{k=0}^n {n\choose k} = 2^n\]
\[ \sum_{k=0}^{\lfloor\frac{n}{2}\rfloor} {n \choose 2k} = 2^{n-1} \]
\[ \sum_{k=0}^m {n-k \choose m-k} = {n+1 \choose m} \]
\[ \sum_{k=0}^m {u \choose k}{v \choose m-k} = {u+v \choose m}\]

I will write explanations for these in a future post.  All of these identities, as well as many others can be found in the book Combinatorial Problems and Exercises.