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