## Binomial coefficients and Pascal's triangle

In a previous post, I introduced binomial coefficients, and we saw that they can be given by the formula $\displaystyle\binom{n}{k} = \frac{n!}{k! (n-k)!}.$

Let’s make a table of binomial coefficient values — that is, we’ll make a table where you can look up a row corresponding to n, a column corresponding to k, and find the value of $\binom{n}{k}$ at the intersection. It’s not too hard (and probably a good exercise) to do by hand for small values, but for now I’ll use J, which I’ve written about before.

   |: !/~ i.12
1  0  0   0   0   0   0   0   0  0  0 0
1  1  0   0   0   0   0   0   0  0  0 0
1  2  1   0   0   0   0   0   0  0  0 0
1  3  3   1   0   0   0   0   0  0  0 0
1  4  6   4   1   0   0   0   0  0  0 0
1  5 10  10   5   1   0   0   0  0  0 0
1  6 15  20  15   6   1   0   0  0  0 0
1  7 21  35  35  21   7   1   0  0  0 0
1  8 28  56  70  56  28   8   1  0  0 0
1  9 36  84 126 126  84  36   9  1  0 0
1 10 45 120 210 252 210 120  45 10  1 0
1 11 55 165 330 462 462 330 165 55 11 1


Note that the first row and column of the table correspond to n=0 and k=0, respectively. So if we wanted to know the value of, say, $\binom{3}{1}$, we would look in the fourth row and the second column to find 3, as expected. If we wanted to know the value of $\binom{4}{2}$, we would look in the fifth row, third column — sure enough, it’s 6.

Notice that the first column (corresponding to k=0) contains all 1’s. Does that make sense? Sure — there’s always only one way to choose nothing! Notice also that all the entries in the upper-right are zero. These are places where k > n. This makes sense too, since, for example, there’s no way to choose 7 things if you only have 3 options. One more interesting thing to note is that each row of the table is symmetric. For example, $\binom{6}{1} = \binom{6}{5}$ and $\binom{6}{2} = \binom{6}{4}$. This makes sense if you think about it — choosing four things out of six (for example) is the same as choosing the two things out of six that you’re not going to choose!

Now let’s do something completely unrelated. Get out a piece of paper, or open Notepad, or whatever. We’re going to write down a bunch of lines containing numbers. Start by writing down a single 1 by itself on the first line. Now for each new line after that, start by writing a 1 in the first column, and then for each subsequent column write a number which is the sum of the number above it and the number above and to the left (if there is no number above, treat it as zero). Remember, this is completely unrelated to binomial coefficients. So the first two rows would look like this:

1
1  1


Pretty exciting, I know. The next row would be 1 2 1 — write down an initial 1, then 1 + 1 is 2, then 1 + 0 is 1. Make sense? Keep going for a few rows. Oh, and did I mention that this is completely unrelated to binomial coefficients?

So if you keep going for a while, you get something that looks like this:

1
1 1
1 2 1
1 3 3  1
1 4 6  4  1
1 5 10 10 5  1
1 6 15 20 15 6  1
1 7 21 35 35 21 7 1


This is known as Pascal’s Triangle, named for the French mathematician and philosopher Blaise Pascal. Keep in mind that Pascal’s Triangle has absolutely nothing whatever to do with binomial coefficients.

Except for the fact, which you have probably guessed by now, that I am a horrible liar. Egads!

At this point you probably have a number of burning questions. Why is the table of binomial coefficients the same as Pascal’s triangle? What on earth does this have to do with tetrahedral numbers? Why do I toy with your mind so? Tune in next time for the exciting conclusion! Assistant Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
This entry was posted in counting, famous numbers. Bookmark the permalink.

### 8 Responses to Binomial coefficients and Pascal's triangle

1. Steve Gilberg says:

I notice that each row adds up to the next power of 2. It makes sense, but it wasn’t immediately obvious to me.

2. Brent says:

True! I’ll probably write about that at some point.

3. Tana says:

I was wondering how Pascals Triangle relates to expected value?

4. Brent says:

Hi Tana,

“Expected value” is a term from probability theory. Giiven some quantity which has a known distribution–that is, a set of possible values with a probability for each–we can ask what the expected value of the quantity is, the value that we expect on average. Computing probabilities, in turn, has a lot to do with counting things: the probability of event A is the number of ways event A can occur divided by the total number of things which can occur. Counting, in turn, quickly leads you to things like binomial coefficients and Pascal’s triangle.

5. Joe says:

Not sure if you are still responding to these posts or if you are even reading them, but anyway… I happen to be on the way out of town to Thanksgiving dinner driving on the freeway with my wife and 2 children sleeping in the car when the song “The twelve days of Christmas” came on. So I thought to myself that to pass the time I would try to come up with a variable expression to represent the total number gifts that had been received on any day of the twelve days … you know, just to pass the time. Well, I got just a stitch farther than n(n+1)/2 in my head. Had I realized that it was going to be this involved I would have tried something else. I teach 7th grade math and this is an awesome explanation. I still don’t quite get how Gauss figures into the final equation, but I’m good with ignorance. I think I will only go as far with my students as having them figure the triangular and tetrahedral numbers through 12. We’ll have them tackle binomial coefficients in the 8th grade. =)

6. Brent says:

Hi Joe, I’m definitely still reading and responding to comments! Thanks for the story, that sounds like the kind of thing I would do to pass the time, too. =) Hope your students have fun!