Pascal's Triangle / Binomial Expansion?

Question

What is the formula for getting the number in the nth row and mth column of Pascal's Triangle (i.e. the one used in Binomial Expansion), and why does it work? (I am more interested in the why part; I can look up the formula easily. I want to understand why it works).

Thanks,
Jack

Answer 1

Hm. There are lots of good sites on the web about Pascal's triangle and the Binomial expansion.

To understand how to get the coefficients, consider as an example trying to compute:

(x + y)³
= (x + y)(x + y)(x + y)
= (xx + xy + yx + yy)(x + y)
= xxx + xyx + yxx + yyx + xxy + xyy + yxy + yyy
= xxx + (xyx + yxx + xxy) + (yyx + xyy + yxy) + yyy

I deliberately didn't simplify to make it clear what is happening.

Notice that all the terms in parentheses are the same (x²y and xy²), and will ultimately add together....

....but also notice that you can think of these four groupings as:

-- The number of ways to form a string of length 3 where each character is an x.
-- The number of ways to form a string of length 3 where two characters are x and the other one is a y.
-- The number of ways to form a string of length three where two characters are y and the other one is an x.
-- The number of ways to form a string of length 3 where each character is a y.

But, when you group them to add them, order no longer makes a difference: xxy = xyx = yxx = x²y, and yyx = yxy = xyy = xy².

So to compute a particular value in the triangle in the nth row and in the mth column, what you are really trying to do is to calculate "how many strings of length n can I create using (n - m + 1) x's and (m - 1) y's"? (the extra +1 and -1 are there so you don't have to call the first column the "0th column".)

For example, take the 4th row, 2nd column. This would be the coefficient of x³y in the binomial expansion of (x+y)^4.

The equivalent question is:

"How many strings of length 4 can you create using (4 - 2 + 1) = 3 x's and (2 -1) = 1 y?"

You could write them all out: xxxy xxyx xyxx yxxx.

Or you can say, I have 4 places for the first x, 3 places for the second x, 2 places for the third x, and only one left for the y, for a total of 4! = 24 arrangements. But since the x's can't be distinguished from each other, you have to divide by the factorial of the number of x's. 4! / 3! = 4.

Hopefully this is familiar to you: it's a combination.

So, in general, to compute the value in the mth column and nth row of the triangle, the formula is:

C(n, m-1) = n! / [(m - 1)! (n - m + 1)!]

Or if you're ok with calling the calling the first column "column zero", then it's simpler:

C(n, m) = n! / [m! ( n - m)!]

Hope that gives you an idea. :)

Answer 2

Well, you can look up that in the nth row, mth column it is
C(n,m) = n! / [(n-m)! m!] where n! is n factorial ( n*(n-1)*(n-2)...3*2*1 )
(There is a 0th row and 0th column in the triangle. C(n,0) = 1)

Each number in the triangle is the sum of the two numbers above it. This can be shown algebraicly,

C(n,m) + C(n, m+1)
= n! / [(n-m)! m!] + n! / [(n-m-1)! (m+1)!]
= { n! / [(n-m-1)! m!] } * { 1/(n-m) + 1/(m+1) }
= { n! / [(n-m-1)! m!] } * { (m+1+n-m) / [(n-m)(m+1)] }
= { n! / [(n-m-1)! m!] } * { (n+1) / [(n-m)(m+1)] }
= (n+1)! /[(n-m)! (m+1)!]
= C(n+1, m+1)

To see how this applies to the binomial expansion, consider

(x+1)^n
Lets say that this equals
a(0)*(x^n)*(1^0) + a(1)(x^(n-1))*(1^1) + ... + a(n) ,
where a(k) = C(n,k)

If we multiply this by another (x+1) , we get:
(x+1)^(n) * (x+1)
= a(0)*(x^(n+1))*(1^0) + a(1)(x^n)*(1^1) + ... + a(n)x
+ a(0)*x^n*(1^0) + a(1)*x^(n-1)*(1^1) + ... + a(n) + 1

= a(0) x^(n+1) + [a(1) + a(0)]x^n + [a(2) + a(1)]x^(n-1) + ... + 1
= (x+1)^(n+1)

So each term is a(k) + a(k-1), in other words, the sum of the two terms above it in Pascal's triangle.

Answer 3

Don't listen to people who tell you that you can't understande unless you remember a formula; it's exactly the other way around, you'll remember formulas better if you understand them.

The formula is C(n, m) = n!/[m!(n-m)!], where the numbering starts at row zero and column zero.

Why? You are essentially looking for the coefficient of a^m*b^(n-m) in the expansion of (a+b)^n. This is the factor (a+b) multiplied n times over.

For example, in (a+b)^2 you get a*a + a*b + b*a + b*b. Each of these 4 terms is obtained by picking either a or b from each (a+b) factor and multiplying.

For (a+b)^n, you pick either a or b from each of the n factors (a+b). You do this 2^n times to get all the possible combinations of either a or b from each. How many ways are there of getting a m times and b (n-m) times? That's exactly like putting the (a+b) factors in a bag and picking the first m to supply the a (and, consenquently, the remaining n-m to supply the b). So, it is exactly like the number of combinations "n choose m".

Answer 4

As you see, the explanations you got above make no sense. Better accept the Pascal triangle as a fact of life and stop worrying.

If you cannot remember such an easy formula, you will never understand the explanation any way.

Answer 5

It's n choose k, or the binomial coeffieient. It's n!/[(n-k)!k!] , n factorial divided by n-k factorial divided by k factorial.

n can be 0, (a+b)^0 = 1 , one term of one value

k = 0 to n.

Answer 6

Depending on which row of the triangle, it gives you the coefficients of the expansion.