Skip to content
Tutorials Center
My learning

Topics

Lesson 33 of 68 ยท Counting

Binomial Theorem and Pascal's Triangle

Expand (x + y)^n with binomial coefficients, build Pascal's triangle, prove identities by counting, and use stars and bars and multinomial coefficients.

Multiply (x + y) by itself and you get xยฒ + 2xy + yยฒ. Do it three times and you get xยณ + 3xยฒy + 3xyยฒ + yยณ. The numbers in front, 1 2 1 and 1 3 3 1, look familiar: they are the values of C(n, r) from Permutations and Combinations. That is not a coincidence, and the reason is a nice piece of counting.

This lesson explains the binomial theorem, arranges the coefficients into Pascal's triangle, and collects the identities that fall out of it. Then it extends the ideas to two further tools: stars and bars, which counts ways to distribute identical items, and multinomial coefficients, which handle expansions of sums with more than two terms.

The binomial theorem

For any non-negative integer n,

(x + y)โฟ = ฮฃ C(n, k) ยท x^(n-k) ยท y^k, summed for k from 0 to n.

Why? Write (x + y)โฟ as n factors multiplied together: (x + y)(x + y)...(x + y). To expand it, pick either x or y from every factor and multiply the choices. A term x^(n-k) y^k appears whenever you chose y from exactly k of the n factors. The number of ways to pick which k factors give y is C(n, k), which is precisely the coefficient. Binomial coefficients really are counting, not just algebra.

Examples: (x + y)โด = xโด + 4xยณy + 6xยฒyยฒ + 4xyยณ + yโด. And setting x = y = 1 gives 2โฟ = ฮฃ C(n, k), which says the numbers of subsets of each size add up to the size of the power set, the fact previewed in Power Sets and Cartesian Products.

Python Expanding (x + y)^n by multiplying polynomials

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The first line of each pair is the coefficient list produced by brute-force polynomial multiplication, and the True shows that it agrees with C(n, k) for every row.

Pascal's triangle

Arrange the binomial coefficients in rows: row n holds C(n, 0), C(n, 1), ..., C(n, n). The result is Pascal's triangle:

Text
        1
       1 1
      1 2 1
     1 3 3 1
    1 4 6 4 1

Each inner entry is the sum of the two entries above it. This is Pascal's rule:

C(n, k) = C(n-1, k-1) + C(n-1, k)

A counting proof makes it obvious. Consider choosing k people from n, and focus on one special person. Either that person is on the team (choose the other k-1 from the remaining n-1) or not (choose all k from the remaining n-1). These cases are disjoint and cover everything, so the sum rule applies.

Python Build Pascal's triangle by Pascal's rule

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Identities worth knowing

The triangle contains many patterns, each with a counting or algebraic explanation.

Patterns in the triangle

Symmetry C(n, k) equals C(n, n-k).
Row sums Row n adds up to 2 to the n.
Alternating sums With signs, each row (n at least 1) sums to 0.
Hockey stick A diagonal run sums to the next number over.
1 / 2
  • Symmetry: C(n, k) = C(n, n-k). Choosing the k you take is the same as choosing the n-k you leave.
  • Row sum: ฮฃ C(n, k) = 2โฟ, from setting x = y = 1.
  • Alternating sum: for n โ‰ฅ 1, ฮฃ (-1)^k C(n, k) = 0, from x = 1 and y = -1. It means the even-sized subsets and the odd-sized subsets are equally numerous.
  • Hockey stick: C(r, r) + C(r+1, r) + ... + C(n, r) = C(n+1, r+1). Adding along a diagonal gives the entry just below and to the side.
  • Vandermonde's identity: C(m+n, r) = ฮฃ C(m, k) ยท C(n, r-k). Choose r people from two groups of sizes m and n by deciding how many come from the first.
Python Checking the identities numerically

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Passing the checks for small ranges is not a proof, but combined with the counting arguments above it builds good confidence. The last loop shows an unexpected pattern in the odd entries. Rows 3, 7 and 15 (one less than a power of two) are entirely odd, while row 8 has only two odd entries; the count of odd entries is always a power of two, which hints at the fractal shape you see when you shade the odd numbers.

Stars and bars

How many ways can you give 10 identical candies to 3 children, where a child may get none? We want the number of non-negative integer solutions of x1 + x2 + x3 = 10.

Picture the 10 candies as stars and put 2 bars to separate the three children:

โ˜…โ˜…โ˜…|โ˜…โ˜…โ˜…โ˜…โ˜…|โ˜…โ˜…

Any arrangement of 10 stars and 2 bars corresponds to one distribution. The arrangement has 12 positions, and we pick which 2 are bars: C(12, 2) = 66. In general, distributing n identical items among k groups, allowing empty groups, can be done in

C(n + k - 1, k - 1) ways

(equivalently C(n + k - 1, n)). This is also the count of multisets of size n from k types, the "unordered with repetition" case of the previous lesson. If every group must receive at least one item, give each group one first, leaving n - k to distribute freely: C(n - 1, k - 1).

Python Stars and bars versus brute force

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Multinomial coefficients

What if you expand a sum of more than two terms, such as (x + y + z)โฟ? The coefficient of x^a y^b z^c, where a + b + c = n, is the multinomial coefficient

n! / (a! ยท b! ยท c!)

This is the same number as the count of arrangements of a word with a copies of one letter, b of another and c of a third (the anagram idea from the last lesson). You can also build it in stages: choose which a of the n factors give x, then which b of the rest give y, giving C(n, a) ยท C(n-a, b).

The sum of all multinomial coefficients in the expansion of (x + y + z)โฟ is 3โฟ, by setting every variable to 1.

Python Multinomial coefficients

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

There are 15 distinct exponent triples that sum to 4 (that is C(6, 2), another stars-and-bars count), and 81 terms in the unexpanded product.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What is the coefficient of x^2 y^3 in the expansion of (x + y)^5?

    The coefficient is C(5, 3) = C(5, 2) = 10: choose which 3 of the 5 factors contribute y.
  2. 2. Which identity is Pascal's rule?

    Choosing k from n splits into teams that include a given person, C(n-1, k-1), and teams that do not, C(n-1, k).
  3. 3. How many non-negative integer solutions does x1 + x2 + x3 + x4 = 7 have?

    Stars and bars: C(n + k - 1, k - 1) = C(10, 3) = 120, with n = 7 stars and 3 bars.
  4. 4. What is the sum of the entries in row 8 of Pascal's triangle (the row that starts 1, 8, 28)?

    Row n sums to 2^n, so row 8 sums to 256.
  5. 5. How many distinct arrangements are there of the letters in MISSISSIPPI?

    11 letters with I x4, S x4, P x2 and M x1: 11! / (4! 4! 2! 1!) = 34,650.

Summary

  • The binomial theorem expands (x + y)โฟ with coefficients C(n, k), because each term comes from picking y from k of the n factors.
  • Pascal's triangle is built with C(n, k) = C(n-1, k-1) + C(n-1, k); its rows are symmetric and sum to 2โฟ.
  • Many identities (alternating sum, hockey stick, Vandermonde) have two-line counting proofs and are easy to sanity-check in Python.
  • Stars and bars counts distributions of identical items: C(n + k - 1, k - 1) with empty groups allowed, C(n - 1, k - 1) with none empty.
  • Multinomial coefficients n!/(a! b! c! ...) count arrangements with repeated items and expand sums of more than two terms.

Next: Advanced Counting, which covers derangements, Catalan numbers, Stirling numbers and integer partitions.