## Combinatorics, Binomial Theorem

### Binomial/Multinomial Theorem

When expanded, the coefficients on the terms of (x+y)n form the nth row of Pascal's triangle.  In other words, the coefficient on xjyn-j is the jth number in the nth row of the triangle.  (Counting starts at zero, not one.)  This can be shown by induction on n.

When (x+y)n-1 is multiplied by x+y, each coefficient in the product, other than xn and yn, is the sum of two coefficients from the previous product.  For example, every instance of x3y6 in (x+y)9 comes from x2y6×x or x3y5×y.  Hence we add the coefficients on x2y6 and x3y5, from (x+y)8, to get the coefficient on x3y6 in (x+y)9.  The coefficients on the terms xn and yn are always 1.  This mirrors the construction of Pascal's triangle perfectly.

 There is another formula for the jth coefficient in the product.  By the distributive law, there are 2n terms, selecting x or y at each step.  The number of terms with j instances of x and n-j instances of y is equal to the number of combinations of j elements, drawn from n elements.  This is n choose j, written (n:j), with formula n!/(j!×(n-j)!).  This means the jth number in the nth row of Pascal's triangle is also (n:j). Since these numbers are the coefficients on the nth power of a binomial, they are often called binomial coefficients. Set x=y=1 and obtain the immediate corollary: 2n is the sum of (n:i) as i runs from 0 to n.  The sum of all the binomial coefficients from 0 to n, or the sum of the entries in the nth row of Pascal's triangle, is 2n.  When x and y are 1 and -1, the alternating sum of binomial coefficients is 0.

The binomial theorem generalizes to the multinomial theorem when the original expression has more than two variables, although there isn't a triangle of numbers to help us picture it.  When x+y+z is raised to the n, there are n!/(i!×j!×k!) ways to arrange i instances of x, j instances of y, and k instances of z.  Hence this combination becomes the coefficient on xiyjzk.

Let's look at (x+y+z)7.  The coefficient on xy2z4 is the number of ways you can arrange xyyzzzz.  That's 7! divided by (1!×2!×4!), or 105.