Counting and Combinations

1 in 292,201,338

Powerball's official prize chart gives the odds of winning the grand prize with one $2 play as 1 in 292,201,338. Where does such an exact number come from? Nobody played the game 292 million times to find out. It comes from counting.

To play, you pick five different white-ball numbers from 1 to 69 and one red Powerball number from 1 to 26. The five white balls can match in any order; the red ball must match exactly. So the count is:

By the end of this unit you'll be able to find the 11,238,513 yourself, and the odds of the other prizes too. The same tools answer questions that have nothing to do with lotteries: how many passwords, how many committees, how likely two people in your class share a birthday.

What you already know

From Probability: when outcomes are equally likely, P(event) = (number of outcomes in the event) ÷ (total number of outcomes). So hard probability questions are often counting questions. You've also seen three counting tools:

• Multiplication principle: m choices, then n choices, give m × n results.
• Permutations (order matters): ₙPₖ = n × (n − 1) × … with k factors.
• Combinations (order doesn't matter): ₙCₖ = ₙPₖ ÷ k!.

This unit adds the reasons behind these formulas, the cases they don't cover, and bigger examples.

The multiplication principle, again

The principle works for any number of steps, as long as the number of choices at each step doesn't depend on what was picked before.

• With repetition allowed: a 4-digit PIN has 10 choices for each digit, so 10 × 10 × 10 × 10 = 10⁴ = 10,000 PINs. In general, k picks from n options with repeats allowed give nᵏ.
• Without repetition: if the 4 digits must all be different, it's 10 × 9 × 8 × 7 = 5,040.
• Mixed steps: a code with 2 letters then 3 digits has 26 × 26 × 10 × 10 × 10 = 676,000 options.

A useful trick is counting the complement. How many 4-digit PINs have at least one repeated digit? Counting those directly is messy. It's all PINs minus those with no repeats: 10,000 − 5,040 = 4,960.

Factorials

The number of ways to line up n different things is n × (n − 1) × … × 2 × 1, written n! (“n factorial”). Five books on a shelf: 5! = 120 orders. Factorials grow very fast: 10! = 3,628,800, and 52! (the orders of a shuffled deck) is about 8 × 10⁶⁷.

Why is 0! = 1? There is exactly one way to arrange nothing: do nothing. It also keeps the pattern working. Since n! = n × (n − 1)!, we get 1! = 1 × 0!, so 0! must be 1. And it makes formulas like ₙCₙ = n! ÷ (n! × 0!) = 1 come out right.

Factorials let us write permutations compactly: ₙPₖ = n! ÷ (n − k)!. The (n − k)! cancels the factors we don't use. For 8 runners and 3 medals, 8! ÷ 5! = 8 × 7 × 6 = 336.

Arrangements with repeats

How many different “words” can you make from the letters of BOOK? If the two O's were different (O₁ and O₂), there would be 4! = 24 arrangements. But swapping O₁ and O₂ gives the same word, so each word was counted 2! = 2 times. The answer is 24 ÷ 2 = 12.

In general, n objects where one kind repeats a times, another b times, and so on, can be arranged in

The same idea gives the combination formula. Choosing 3 of 8 people is like arranging 3 “in” labels and 5 “out” labels: 8! ÷ (3! × 5!) = 56.

Combinations and why they divide

ₙCₖ, also written as the binomial coefficient (n choose k), counts the ways to choose k of n things when order doesn't matter:

Every group of k can be put in order in k! ways, so the ordered count ₙPₖ is k! times too big. Dividing by k! fixes it.

• Symmetry: ₙCₖ = ₙCₙ₋ₖ. Choosing 3 people to go is the same as choosing the 5 who stay: ₈C₃ = ₈C₅ = 56.
• Edges: ₙC₀ = ₙCₙ = 1. There's one way to choose nobody, and one way to choose everybody.
• Several groups: multiply. A team of 2 seniors from 6 and 3 juniors from 7: ₆C₂ × ₇C₃ = 15 × 35 = 525.

Pascal's triangle

Write 1 at the top. Each row starts and ends with 1, and every other entry is the sum of the two entries above it. Row n (counting the top row as row 0) lists ₙC₀, ₙC₁, …, ₙCₙ.

Why the sum rule works: to choose k of n people, single out one person, Ana. Either Ana is chosen (then pick k − 1 of the other n − 1) or she isn't (pick all k from the other n − 1). So ₙCₖ = ₙ₋₁Cₖ₋₁ + ₙ₋₁Cₖ.

The triangle gives the binomial coefficients: the numbers in (a + b)ⁿ. For example, (a + b)⁴ = a⁴ + 4a³b + 6a²b² + 4ab³ + b⁴, using row 4: 1, 4, 6, 4, 1. They're the same numbers as in the binomial distribution: the chance of exactly k heads in n fair coin flips is ₙCₖ ÷ 2ⁿ. Adding a whole row gives 2ⁿ, the number of possible subsets.

Lottery odds

Counting also gives the smaller prizes. Take “match all 5 white balls but not the Powerball”. You must pick the 5 winning white numbers (1 way out of 11,238,513) and one of the 25 losing red numbers:

That matches the official chart, which lists 1 in 11,688,053.52 for the $1 million prize. Here's a harder one: match exactly 4 white balls and the Powerball. Choose 4 of the 5 winning white numbers (₅C₄ = 5), 1 of the 64 losing ones (64), and the 1 winning red number:

That's the official odds for the $50,000 prize. Every line of the chart can be checked this way.

A sense of scale: buying 100 tickets for every drawing, three drawings a week, you'd expect to wait about 292,201,338 ÷ 300 ≈ 974,000 weeks, roughly 18,700 years, for a jackpot.

The birthday problem

How many people must be in a room before there's a better than even chance that two share a birthday? Most people guess around 183. The answer is 23.

Assume 365 equally likely birthdays (ignore February 29 and seasonal patterns). The trick is the complement: count the ways that everyone's birthday is different.

• All ways for n people: 365ⁿ.
• All different: 365 × 364 × 363 × … (n factors) = ₃₆₅Pₙ.
• P(at least one shared) = 1 − ₃₆₅Pₙ ÷ 365ⁿ.

For n = 23 this is 1 − 0.4927 ≈ 0.507. With 50 people it's about 0.970, and with 70 about 0.999. The surprise comes from the number of pairs: 23 people make ₂₃C₂ = 253 pairs, and any one of them can match.

Poker hands

A poker hand is 5 cards from a 52-card deck, and order doesn't matter, so there are ₅₂C₅ = 2,598,960 hands. Count a hand type, divide by this, and you have its probability.

This is why a full house beats a flush: there are fewer of them. Notice the full house uses 12, not 13, for the pair, because the pair can't be the same rank as the three.

Which tool?

Common mistakes

• Using permutations for a group. Ask: does swapping two picks change the result? If not, divide by k!.
• Forgetting to divide for repeated letters. The two O's in BOOK are not different.
• Adding when you should multiply. “This and then that” multiplies; “this or that” (with no overlap) adds.
• Counting “at least one” directly. It's usually easier as 1 − P(none).
• Double counting. In the full house, the pair's rank has 12 choices, not 13.
• Assuming equally likely outcomes when they aren't. Counting gives probabilities only when every outcome is equally likely.

Practice

History

• 1000s The Chinese mathematician Jia Xian (1010–1070) works with the triangle of numbers now often called Pascal's triangle.
• 1200s Yang Hui (1238–1298) describes the triangle; in China it is known as Yang Hui's triangle.
• 1303 Zhu Shijie's Jade Mirror of the Four Unknowns shows the triangle drawn in rod numerals.
• 1654 Blaise Pascal and Pierre de Fermat exchange letters that lay the foundations of probability (see Probability).
• 1665 Pascal's Traité du triangle arithmétique is published after his death. He was not the first to study the triangle, but his treatise collected its properties and used them for probability problems.

Quiz

Ten questions. Pick an answer for each, then check.