Box 4.1.1 More on Binomial CoefficientsKCT logo

© 1996 by Karl Hahn

How Do You Compute Binomial Coefficients?

We have already seen that we can determine a binomial coefficient for the n + 1st row of table 4b-1 provided we already know what they are for the nth row. Is there a way you can figure out what a binomial coefficient is without having to know what they are on the previous row?

Since we shall be referring frequently to table 4b-1, here it is again:

Table 4b-1: Binomial Coefficients (n £ 12) 
  n:      b0   b1   b2    b3   b4   b5   b6    b7   b8   b9   b10  b11   b12
  1:       1    1
  2:       1    2    1
  3:       1    3    3    1
  4:       1    4    6    4    1
  5:       1    5   10   10    5    1
  6:       1    6   15   20   15    6    1
  7:       1    7   21   35   35   21    7    1
  8:       1    8   28   56   70   56   28    8    1
  9:       1    9   36   84  126  126   84   36    9    1
 10:       1   10   45  120  210  252  210  120   45   10    1
 11:       1   11   55  165  330  462  462  330  165   55   11    1
 12:       1   12   66  220  495  792  924  792  495  220   66   12    1

As we have already seen, binomial coefficients are different for each new n. So here I am going to introduce a new notation for them. b(n, k) indicates the entry in the nth row, kth column of table 4b-1. Here is a formula that will always work for finding b(n, k): 

               ænö          n!
   b(n, k)  =  èkø  =                                            eq. 4c-1
                       k! (n - k)!

(Note that the more traditional notation for binomial coefficients, that is the notation with the parentheses, has been included in the above equation. When you see this notation in math books, this is what it is referring to.)

As you know, the expression, n!, where n is a counting number, indicates the product of all the counting numbers from 1 up to and including n. This product is called n factorial. The formula only works if you can accept that 0! = 1. I know that doesn't seem intuitive, but there's a whole lot of things in mathematics that work well if you use that definition of 0!, and they don't work if you use any other definition.

A clear formula that arises out of factorials is: 

   (n + 1) n!  =  (n + 1)!                                       eq. 4c-2
We'll be using that in just a little while.

Try putting in 0 for k and anything you like for n into equation 4c-1. Do you see how the way we've set things up, this always gives you b(n, 0) = 1? And that is what we expect we should get from our previous discussion about binomial coefficients. The formula says that the left-hand column of table 4b-1 must contain all 1's.

And what about the last entry in each row? We already determined that it was also always 1. Does the formula work for that? Pick an n, and use 4c-1 to find b(n, n).

We also have what's called a recursion formula. That is, we know a formula that, by using values from a previous row of table 4b-1, we can find values for a subsequent row. If we translate the recursion formula into our new notation, we have: 

   b(n+1, k)  =  b(n, k-1) + b(n, k)                             eq. 4c-3
(Here's the same thing in the more traditional notation)
   æn+1ö     æ n ö     ænö
   è k ø  =  èk-1ø  +  èkø                                         eq. 4c-3a
Of course, for 4c-3 to work, you must have k > 0.

So does the formula in 4c-1 comply with the rule given by 4c-3? Let's see by substituting into 4c-3 from 4c-1: 

       (n + 1)!                   n!                   n!
                    =                           +            
   k! (n + 1 - k)!     (k - 1)! (n - (k - 1) )!   k! (n - k)!

                                                                 eq. 4c-4
The question is, can we prove that 4c-4 always holds? Well, first notice that n - (k - 1) = n + 1 - k. So we can rewrite 4c-4 as: 
       (n + 1)!                   n!                 n!
                    =                         +            
   k! (n + 1 - k)!     (k - 1)! (n + 1 - k )!   k! (n - k)!

                                                                 eq. 4c-5
So now, algebra demands that we put the two summands over a common denominator. This is where we can use the identity given in 4c-2. We shall multiply both numerator and denominator of the first summand by k. We shall multiply both numerator and denomonator of the second summand by n + 1 - k (remember that n + 1 - k is just 1 more than n - k). If we do that and apply 4c-2, we get: 
       (n + 1)!              k n!         (n + 1 - k) n!
                    =                   +                
   k! (n + 1 - k)!     k! (n + 1 - k )!   k! (n + 1 - k)!

                                                                 eq. 4c-6
We now have our common denominator. Multiply out the numerator of the second summand to ( (n + 1) n!) - (k n!) before you add the numerators. You will see a cancellation, leaving you with: 
       (n + 1)!           (n + 1) n!
                    =                                            eq. 4c-7
   k! (n + 1 - k)!     k! (n + 1 - k )!
Now simply apply 4c-2 to the numerator of the right hand side, and equality is proved.

If you review the main points of what we just did, you will see that it constitutes proof by induction that the formula given in 4c-1 will always give identical numbers for binomial coefficients as the recursion formula does.

Lotto Numbers

In many states in the U.S., the state government plays a little game of chance with all those who would part with $1 for a ticket. For that price, you pick six of the numbers between 1 and, say, 46 (the actual highest number you can pick varies from state to state). None of your six picks may be repeats of any of the other five.

Once per week, the state lottery commission fires up a machine that has 46 ping pong balls in it, numbered from 1 to 46. The machine blows them about randomly, and then a smiling young lady flips six levers that allow six of the balls to pop into six slots. Those are the winning numbers for the week. Anybody who has purchased a ticket that week with those numbers, in any order, wins a big cash prize.

The odds at this game are clearly related to the number of ways you can pick 6 objects out of a possible 46. It turns out that the number of ways you can do that is, in fact, b(46, 6). If you poke those numbers in on a calculator using the formula in 4c-1, you get that the number of ways to make out your ticket is 9,366,819. And, of course, the probability of any ticket being a winner is only one out of that number.

But the interesting thing is how the 4c-1 works to give us this number. For the first number I pick making out a ticket, I can choose any of 46 possibilities. But for the second number, I have already used up one of the 46 numbers, so there are only 45 left I can choose from. And for the third selection, there are only 44 left, and so on. So the total number of ways I can pick is: 46 × 45 × 44 × 43 × 42 × 41. But remember that whether I win or not is independent of what order I pick the numbers in. There are 6! ways of ordering 6 objects. The way I have computed my number of ticket choices counts each ordering separately. So I have to divide the product of 46 through 41 by 6! in order to get the number of possible ways to make out a ticket. So the number I am after is: 

   46 × 45 × 44 × 43 × 42 × 41
                                =  9,366,819
      6 × 5 × 4 × 3 × 2 × 1
If you work out carefully what is meant by 4c-1 (and what cancellations it always gives you), you will see that it is expressing the same thing.

The lotto problem is just one of many examples where binomial coefficients turn up in probability and statistics.

Return to Box 4.1

email me at hahn@netsrq.com