Just counting

As I already mentioned in a previous post, many people get intimidated by a problem if it contains unfamiliar notation.  Indeed, even for mathematicians, it often takes some time to start feeling comfortable with new terminology and abstract concepts.  In this post I would like to get the reader to feel at home with the \({n \choose k}\) notation that I used in my first post.  Often, a good way of doing this is to think about specific objects and quantities rather than abstract ones.

So imagine you walk into an ice cream store and there are five flavors available.  You realize that you like them all equally.  How many different ice cream cones can you end up with if you only want one scoop (this is a small local shop so there is only one type of cone)? Let us denote this quantity by \({5 \choose 1}\) (pronounced "five choose one").  Clearly, \({5 \choose 1} = 5\), the number of flavors.  Your friend, on the other hand (did I mention you brought five friends with you?), wants two scoops on her cone, not both of the same flavor.  How many different cones can she end up with (two cones are the same if they contain the same flavors)?  We can compute this quantity, denoted by \({5 \choose 2}\) ("five choose two"), by noting that she has five choices for the first flavor and four choices for the second one (given the first choice).  Now $5 \times 4=20$, but we have over-counted because by choosing pistachio first and strawberry second she ends up with the same cone as if she chose strawberry first and pistachio second.  Hence, we need to divide by 2, and so ${5 \choose 2} = 10$.  Now your second friend wants exactly three scoops, all of distinct flavors.  We can compute this in a similar fashion, or we can just observe that choosing three flavors is equivalent to 'not choosing' two flavors.  Hence, ${5 \choose 3} = {5 \choose 2} = 10$.  You might have already guessed that your third friend wants exactly four scoops of distinct flavors, and again observing that choosing four flavors is equivalent to not choosing one, we get ${5 \choose 4} = {5 \choose 1} = 5$.  Your fourth friend wants five scoops and your fifth friend wants zero scoops, just an empty cone.  We can trivially see that ${5 \choose 5} = {5 \choose 0} = 1$.  Luckily you have no sixth friend and so we're done with discussing ice cream!

Now there is nothing special about ice cream or the number five here.  In general, ${n \choose k}$ denotes the number of ways we can select $k$ elements from a set of $n$ elements.  I would like to finish this post by making another attempt at explaining the formula from my first post: \[{n \choose k} = {n-1 \choose k} + {n-1 \choose k-1}.\]

Again, we do this by considering a specific scenario and concrete numbers.  Five thousand students applied to university Uni (it's a very small school) and the size of the freshman class is to be one thousand.  Uni accepts its students completely by lottery.  The question is how many different freshman classes can they end up with?  In our notation from above, this is \({5000 \choose 1000}\).  Now Stu is one of the students who applied to Uni.  Every possible freshman class will either contain Stu or not contain him.  The total number of possible classes is the number of possible classes that contain Stu plus the number that do not contain him.  The number of possible classes that do not contain Stu is ${4999 \choose 1000}$ because we want a class of 1000 students and we are choosing from everyone minus Stu.  The number of possible classes that contain Stu is ${4999 \choose 999}$ since we need to choose 999 from everyone minus Stu.  Hence, \[{5000 \choose 1000} = {4999 \choose 1000} + {4999 \choose 999}.\]  Now replace 5000 by $n$ and 1000 by $k$!

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.