Pascal's Triangle and Binomial Coefficients

Date: 09/11/2001 at 16:37:51
From: Michelle
Subject: Binomial coefficients and pascals triangle

Why are Pascal's triangle and binomial coefficients the same?  I 
understand how to construct Pascal's triangle, and how the numbers in 
the triangle correspond to the numbers when a binomial is expanded, 
but why are they the same?

Date: 09/12/2001 at 16:29:32
From: Doctor Greenie
Subject: Re: Binomial coefficients and pascals triangle

Hi, Michelle -

Let's start with a familiar problem that isn't closely related to 
either Pascal's triangle or binomial coefficients:

     How many distinct arrangements are there in the letters in 
     MATHEMATICS?

The answer, as you probably know, is

         11!
    ------------
    (2!)(2!)(2!)

where the numerator 11! (eleven factorial) is because there are 11 
letters in all, and the three 2!s in the denominator are because of 
the fact that three of the letters (M, A, and T) appear 2 times each.

Next, let's consider a special type of this problem in which there are 
only two different letters:

     How many distinct arrangements are there in the letters in 
     AAAAABBB?

The number of distinct arrangements in this case is

        8!
    --------
    (5!)(3!)

This number is equivalent to the binomial coefficients C(8,3) and 
C(8,5).

We have shown (informally, by example) that the binomial coefficient 
C(m,n) is equal to the number of distinct arrangements of n identical 
objects of one kind and m-n identical objects of a second kind. If we 
can now show that the number of distinct arrangements of n identical 
objects of one kind and m-n identical objects of a second kind is also 
a specific entry in Pascal's triangle (as formed from the coefficients 
in the expansion of (x+y)^n), then we will have shown the equivalence 
of the entries in Pascal's triangle and the binomial coefficients.

To show the equivalence of the entries in Pascal's triangle and the 
number of distinct arrangements of n identical objects of one kind and 
m-n identical objects of a second kind, let's look at the expansion of 
(x+y)^n, using an extension of the familiar FOIL method for 
multiplying binomials.

When we multiply (x+y)(x+y) using the FOIL method, we have

    (x+y)(x+y)
  = (x)(x)    [F = first term in each factor]
  + (x)(y)    [O = "outer terms" - i.e., 1st term in 1st factor,
                 2nd term in 2nd factor]
  + (y)(x)    [I = "inner terms" - i.e., 2nd term in 1st factor,
                 1st term in 2nd factor]
  + (y)(y)    [L = last term in each factor]
 ---------------
  = x^2+2xy+y^2

The FOIL method is just a special case of a general rule for 
multiplying polynomials which says that the product of the two 
polynomials is the sum of all the "partial products" that can be 
obtained by choosing one of the terms from each of the factors.

Here is the multiplication (x+y)(x+y) again, presented as the sum of 
all the possible "partial products":

    (x+y)(x+y)
  = (x)(x)    [term 1 from factor 1; term 1 from factor 2]
  + (x)(y)    [term 1 from factor 1; term 2 from factor 2]
  + (y)(x)    [term 2 from factor 1; term 1 from factor 2]
  + (y)(y)    [term 2 from factor 1; term 2 from factor 2]
 ---------------
  = x^2+2xy+y^2

Now let's look at (x+y)^3, using the idea of the sum of all the 
possible partial products. In each of the three factors, there are two 
choices for the term to pick; this gives 2^3 = 8 partial products.  
The partial products, and the choices for the terms in each of the 
three factors, are shown in the following table:

      (a,b,c) =
    term number in
     factors 1-3       partial product
    -----------------------------------
      (1,1,1)         xxx = x^3
      (1,1,2)         xxy = x^2y
      (1,2,1)         xyx = x^2y
      (1,2,2)         xyy = xy^2
      (2,1,1)         yxx = x^2y
      (2,1,2)         yxy = xy^2
      (2,2,1)         yyx = xy^2
      (2,2,2)         yyy = y^3
                     ----------------------------
                     = x^3 + 3x^2y + 3xy^2 + y^3

The coefficient of the x^3 term is 1, corresponding to the single 
possible arrangement of the letters xxx; the coefficient of the x^2y 
term is 3, corresponding to the three possible arrangements of the 
letters xxy; the coefficient of the xy^2 term is 3, corresponding to 
the three possible arrangements of the letters xyy; and the 
coefficient of the y^3 term is 1, corresponding to the single possible 
arrangement of the letters yyy.

Let's look at one more example, (x+y)^4, again, using the idea of the 
sum of all the possible partial products. In each of the four factors, 
there are two choices for the term to pick; this gives 2^4 = 16 
partial products. The partial products, and the choices for the terms 
in each of the four factors, are shown in the following table:

     (a,b,c,d) =
    term number in
     factors 1-4       partial product
    -----------------------------------
      (1,1,1,1)         xxxx = x^4
      (1,1,1,2)         xxxy = x^3y
      (1,1,2,1)         xxyx = x^3y
      (1,1,2,2)         xxyy = x^2y^2
      (1,2,1,1)         xyxx = x^3y
      (1,2,1,2)         xyxy = x^2y^2
      (1,2,2,1)         xyyx = x^2y^2
      (1,2,2,2)         xyyy = xy^3
      (2,1,1,1)         yxxx = x^3y
      (2,1,1,2)         yxxy = x^2y^2
      (2,1,2,1)         yxyx = x^2y^2
      (2,1,2,2)         yxyy = xy^3
      (2,2,1,1)         yyxx = x^2y^2
      (2,2,1,2)         yyxy = xy^3
      (2,2,2,1)         yyyx = xy^3
      (2,2,2,2)         yyyy = y^4
                     --------------------------------------
                     = x^4 + 4x^3y + 6x^2y^2 + 4xy^3 + y^4

The coefficient of the x^4 term is 1, corresponding to the single 
possible arrangement of the letters xxxx; the coefficient of the x^3y 
term is 4, corresponding to the four possible arrangements of the 
letters xxxy; the coefficient of the x^2y^2 term is 6, corresponding 
to the six possible arrangements of the letters xxyy; the coefficient 
of the xy^3 term is 4, corresponding to the four possible arrangements 
of the letters xyyy; and the coefficient of the y^4 term is 1, 
corresponding to the single possible arrangement of the letters yyyy.

These examples demonstrate that the coefficient of the x^ny^(m-n) term 
in the expansion of (x+y)^m is equal to the number of distinct 
arrangements of (n) x's and (m-n) y's; and we know this number is 
C(m,n). This completes the demonstration of the equivalence of the 
binomial coefficients and the entries in Pascal's triangle.

**********

Here is a little bonus that comes from the preceding examination of 
the expansion of (x+y)^n as the sum of all the possible partial 
products....

You may be familiar with the fact (as evidenced in Pascal's triangle) 
that

    C(n,0) + C(n,1) + C(n,2) + ... + C(n,n-1) + C(n,n) = 2^n

This fact is nicely shown in the preceding discussion, because, in the 
expansion of (x+y)^n, the C(n,i) are the coefficients of the different 
terms, while the sum of all these coefficients is the total number of 
partial products, which we know is 2^n.

Write back if you have any further questions on this.

- Doctor Greenie, The Math Forum
  http://mathforum.org/dr.math/