EulerPad

Guides / Probability

Counting and the binomial theorem: multiply the choices, divide out the orders that don't matter, and expand with C(n, k)

Most probability on equally likely outcomes is counting: the chance of an event is the number of outcomes in it over the number of outcomes in all. Nobody lists them. Choices made one after another multiply, an ordered selection is a permutation, and an unordered one divides the permutations by the number of orders. The same counts C(n, k) are the coefficients in (x + y)n, which is why they also run the binomial distribution. Most wrong answers come from counting orders that don't matter, losing a power inside a binomial term, or counting a case more than once.

Short answer

Multiply: a ways, then b ways, gives ab ways. Order matters: P(n, k) = n!/(n − k)! = n(n − 1)⋯(n − k + 1). Order doesn't: C(n, k) = n!/(k!(n − k)!), the permutations divided by k!. Repeated letters: n!/(n1! n2! ⋯). Binomial theorem: (x + y)n = Σ C(n, k) xn−kyk, with k from 0 to n.

Why it works

An ordered list of k items from n is built one slot at a time: n choices for the first, n − 1 for the second, and so on, which multiplies to P(n, k). Each unordered group of k items appears in that count once for every way to line it up, and k items line up in k! ways, so dividing by k! counts each group once. That is all C(n, k) is.

Expanding (x + y)n means picking x or y from each of the n factors and multiplying. A term xn−kyk comes from choosing which k factors give the y, and there are C(n, k) ways to choose them. Setting x = y = 1 gives Σ C(n, k) = 2n, the number of subsets of n things.

Example 1: officers against a committee

A club of 12 people picks a president, a vice president and a treasurer. How many ways? How many ways to pick a plain three-person committee instead?

  1. 12 · 11 · 10 = 132012 choices for president, then 11 left for vice president, then 10 for treasurer.
  2. P(12, 3) = 1320The same count as 12!/9!: the roles make the order matter.
  3. 3! = 6Any three people can fill the three roles in 6 ways.
  4. C(12, 3) = 1320/6A committee has no roles, so each group was counted 6 times above.
  5. C(12, 3) = 2201320 ordered slates, 220 committees. Check: 12 · 11 · 10/(3 · 2 · 1) = 220.

Example 2: arranging letters that repeat

How many different strings can be made by rearranging all eleven letters of MISSISSIPPI?

  1. 11! = 39,916,800The count if all eleven letters were different.
  2. I: 4, S: 4, P: 2, M: 1Count each letter. The counts add to 11.
  3. 4! · 4! · 2! = 1152Swapping identical letters among themselves gives the same string, so each string was counted this many times.
  4. 11!/1152 = 34,650The multinomial coefficient 11!/(4! 4! 2! 1!).

Example 3: one term of a binomial expansion

Find the constant term of (x2 − 2/x)6.

  1. C(6, k)(x2)6−k(−2/x)kThe general term, with x2 in the role of x and −2/x in the role of y.
  2. = C(6, k)(−2)kx12−3kThe powers of x: 2(6 − k) − k = 12 − 3k. The −2 keeps its power k.
  3. 12 − 3k = 0, so k = 4A constant term has x0.
  4. C(6, 4) = 156!/(4! 2!).
  5. (−2)4 = 16An even power, so the sign is +.
  6. 15 · 16 = 240Check by expanding in full: the terms run x12 − 12x9 + 60x6 − 160x3 + 240 − ⋯.

Example 4: a probability from counts

A fair coin is flipped 8 times. What is the chance of exactly 3 heads?

  1. 28 = 256Each flip has 2 outcomes, and all 256 sequences are equally likely.
  2. C(8, 3) = 56A sequence with 3 heads is fixed by which 3 of the 8 flips are heads.
  3. 56/256 = 7/32Favorable over total.
  4. P(3 heads) ≈ 0.219This is the binomial formula C(n, k)pk(1 − p)n−k with p = 1/2. Check: C(8, 0) + ⋯ + C(8, 8) = 256.

Common mistakes, and the exact line they happen on

1. Counting orders when order doesn't matter

The committee of Example 1.

  1. 3 people from 12Right so far: no roles, so order doesn't matter.
  2. 12 · 11 · 10 = 1320This is the mistake. This counts the group {Ana, Ben, Cy} once as Ana-Ben-Cy, once as Ben-Ana-Cy and so on, six times in all. Ask whether swapping two picks gives a different outcome. For a committee it doesn't, so divide by 3! = 6 and get 220.

2. Dropping the power on a coefficient

The constant term of Example 3.

  1. k = 4, C(6, 4) = 15Right so far.
  2. 15 · (−2) = −30This is the mistake. The whole second term −2/x is raised to the power k, so the coefficient is (−2)4 = 16, not −2. The sign and the size are both wrong: the answer is 240. Carry the coefficient inside the parentheses until the end.

3. Choosing one, then the rest, for "at least one"

A committee of 3 is chosen from 4 women and 6 men. How many committees have at least one woman?

  1. 10 people, choose 3Right so far.
  2. 4 · C(9, 2) = 144This is the mistake. Picking "the" woman first and then any 2 of the other 9 counts a committee with two women twice, once for each woman picked first. There are only C(10, 3) = 120 committees in all, so 144 can't be right. Use the complement: 120 − C(6, 3) = 120 − 20 = 100.

Practice

  1. In how many orders can 6 different books stand on a shelf?

    Show answer

    6! = 720.

  2. How many ways are there to choose 4 toppings from 9?

    Show answer

    C(9, 4) = 126.

  3. Find the coefficient of x3 in (1 + 2x)6.

    Show answer

    C(6, 3) · 23 = 20 · 8 = 160.

  4. How many different strings can be made by rearranging the letters of BANANA?

    Show answer

    6!/(3! 2! 1!) = 60: three A's, two N's and one B.

  5. A 4-digit PIN uses the digits 0 to 9, repeats allowed. What is the chance all four digits are different?

    Show answer

    10 · 9 · 8 · 7/104 = 5040/10,000 = 0.504.

Practice this

Printable PDF: counting-and-the-binomial-theorem.pdf

Related guides

All guides