## BINOMIAL COEFFICIENTS

A binomial is an algebraic expression with two terms, like x + y. When we multiply out the powers of a binomial we can call the result a binomial expansion.

Of course, multiplying out an expression is just a matter of using the distributive laws of arithmetic, a(b+c) = ab + ac and (a + b)c = ac + bc. In the examples below, I have multiplied out a few binomial expansions, without combining like terms or even writing products as powers. To make things easier to see, I have used a different color for the terms in each factor, so that you can see where they came from.

Notice that each term of the binomial expansions is a product composed of one item of each color. This suggests another way to look at this process of multiplication. Think of each factor in the product as a box containing two items, an x and a y (the colors are used here to keep track of which box an x or a y came from). We form one of the terms in the binomial expansion by picking either an x or a y from each of the boxes and multiplying our selections together. Since there are 2 choices for what we can pick from each of the boxes, the total number of possible different selections is 2x2x2 ... x2, where there are as many 2's as boxes. So, for two boxes there are 2x2 = 4 possibilities, for three boxes there are 2x2x2 = 8 possibilities, and for n boxes there are 2^n possibilities. Now look at the examples again, and notice that the number of terms in the binomial expansions is exactly the total number of possiblities, i.e., for the cube there are 8 terms, for the 4th power there are 16 terms, etc. This means that every possible way of choosing one item from each box gives a term in the binomial expansion.

Now lets group like terms together (but don't combine them just yet). For the 4th power this would give us:

We would like to be able to say exactly how many terms are in each group (this would be the coefficient of the term if it was written out in the normal way). We can do this by counting because we know how the terms are formed. To get a term with, say, 3 x's and 1 y, all we have to do is decide which box we are going to pick the y from and then pick the x's from all the other boxes. Thus, the number of terms of this type is the number of ways we can pick 1 (box) from a set of 4 (boxes). This is the number of subsets of size 1 in a set of size 4 (there are 4 of course). The notation for this number is C(4,1). In general the number C(n,k) is the number of subsets of size k in a set of size n. Looking at the group of terms having 2 x's and 2 y's, we know that we get them by picking 2 of the 4 boxes to take the y's from, so there are C(4,2) = 6 such terms. Now, consider the first and last terms of this example. In order to get xxxx, you don't pick any boxes to take y's from, and you can only do this in one way, so C(4,0) = 1 (there is only one subset of size 0 in a set of size 4 - the empty set). Similarly, to get yyyy, you must pick all the boxes to take y's from, and again there is only one way to do this so C(4,4) = 1. These two statements are true for any number of boxes, so C(n,0) = C(n,n) = 1 for any n.

We can now drop the colors and write things normally to get:

The general case can be written as:

Because the numbers C(n,k) appear as the coefficients of the terms in a binomial expansion, they are called binomial coefficents.

Let's look at one of these multiplications with the binomial coefficients. In the example below

we see how, when we multiply by a new factor of (x+y), the coefficients are formed in the new answer. This example shows where the formation rule for Pascal's triangle comes from. In general, this formation rule can be written as:

C(n,k) = C(n-1, k-1) + C(n-1, k).

To make things a little neater, we define C(n,k) to be 0 if k < 0 or if k > n. With this convention, the formation rule works even at the ends of the rows.