Associated Topics || Dr. Math Home || Search Dr. Math

### 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/
```
Associated Topics:
High School Permutations and Combinations
High School Polynomials

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search