Pascal's Triangle and Binomial CoefficientsDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2015 The Math Forum
http://mathforum.org/dr.math/