Today I’m going to talk about something pretty nifty called binomial coefficients. It may not be immediately apparent to you why they’re so nifty, but take my word for it: they show up all over the place in mathematics! [And yes, if you’re wondering, we’re still on our way towards a formula for tetrahedral numbers. It will become apparent what binomial coefficients have to do with it later.]

In general, a binomial coefficient looks like this: . You pronounce that as “n choose k“, since the simplest way to understand this binomial coefficient is that it tells you how many ways there are to choose k things out of n possible choices. This is known as the number of combinations. (On many calculators, you enter binomial coefficients using a key or function like nCr — C for Combinations.) This definition is enough to let us figure out what some binomial coefficients are for small values of n and k. For example, if I have three things (say, a guava, a starfruit, and a mango) and tell you to choose one, how many different choices do you have? Obviously, three. So . How about if I have four things (say, an Apple, a Banana, a Cherry, and a Date) and ask you to choose any two — how many ways can you make your choice? If we use the first letter of each fruit as an abbreviation, you have six choices: AB, AC, AD, BC, BD, or CD. (Notice that the order in which you pick the two fruits doesn’t matter: AB is the same as BA.) So, .

When we start getting into bigger numbers, however, this gets cumbersome: how can we be sure that we haven’t missed a possible choice? What if the number of choices is so large that it would take us ten years to count them? What we need is a formula which can tell us the value of directly.

To get there, let’s start with something a bit simpler. Say you have n different fruits (an Apple, a Banana, a Cherry, a Date, a… um… an Egg… uh…). How many ways can you line them up in a row, putting one particular fruit first, one second, and so on? Imagine placing them one by one. For the first fruit, you can choose any one of them, so you have n choices. For the second fruit in the line, you can no longer choose the one that’s first, so you only have (n – 1) choices. Then for the third fruit you have (n – 2) choices, and so on, until for the last fruit you only have one choice, since it’s the only one left. In total, then, you have ways of putting your fruits in order. (The exclamation point represents the factorial function.) So, for example, if you have only three fruits, you have ways of putting them in order: ABC, ACB, BAC, BCA, CAB, CBA. For four fruits, there are ways of putting them in order. I won’t bother writing them all out here, but feel free to verify this for yourself. It should be obvious that this argument extends to non-fruit objects as well. =)

Now for another, related question: suppose you take your n fruits, and you want to line them up as before, but you only want to make a line of k fruits out of the total n? Again, you have n choices for the first fruit, (n – 1) choices for the second, and so on, except this time you stop after the kth fruit, for which there will be (n – k + 1) choices — so the total number of ways to do this is . Notice we can write this as :

For example, . What we’re doing here is counting permutations; often on calculators you will see this function called nPr.

We’re almost there. We now have a way of counting the number of ways to choose k things out of a total of n, when we consider each possible order of the k things to be different. But really what we want is a way to count the number of ways to choose k things out of n when the order doesn’t matter. Starting with what we have (counting each order separately), it’s clear that we’re counting each possible group of k things multiple times, one for each possible order. Well, how many ways are there to put k things in order? You got it, k!. So we’re counting each group of k things k! times when we really only want to count it once. Well, that’s easy to fix: just divide everything by k!. Here, finally, is our formula for finding a binomial coefficient:

Let’s check to make sure this formula squares with the small examples we did before. , check! , check!

Hmm… I wonder how many ways there are to choose 4 things out of 10 possibilities? Let’s see: . Now you know. I sure wouldn’t have wanted to count all those possibilities by hand!

Now hold onto your hats — now that we know the basics, next time I’ll show you something truly amazing about binomial coefficients!