Counting without counting
Tonight's idea
Start with the multiplication principle: if a first choice can be made in \(m\) ways and, after each of those, a second choice can be made in \(n\) ways, the pair can be made in \(mn\) ways. The choices need not be independent: a two-letter code with no repeat has \(26 \times 25 = 650\) possibilities, even though the second letter depends on the first. What matters is that every first choice leaves the same number of next choices; if the branch sizes differ, count each branch and add.
Permutations (order matters). Arranging \(n\) different things in a row: \(n\) choices for first place, \(n-1\) for second, and so on: \(n!\). Choosing and arranging \(k\) of them: \(n(n-1)\cdots(n-k+1) = \dfrac{n!}{(n-k)!}\).
Combinations (order does not matter). Choosing \(k\) of \(n\) things as a set: count the ordered choices, then notice every set has been counted \(k!\) times, once per ordering. So \[\binom{n}{k} = \frac{n!}{k!\,(n-k)!}.\] Read "\(n\) choose \(k\)". \(\binom{5}{2} = 10\). We take \(0! = 1\), because there is exactly one way to choose nothing.
The binomial theorem. Expand \((a+b)^n\) by picking \(a\) or \(b\) from each of the \(n\) brackets. The term \(a^{n-k}b^k\) arises once for each way of choosing which \(k\) brackets supply a \(b\): \[(a+b)^n = \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k.\] (The sign \(\sum\) means: add up the terms for \(k = 0, 1, \ldots, n\).) Those coefficients are the rows of Pascal's triangle.
Watch one: MISSISSIPPI
How many distinct arrangements of the letters of MISSISSIPPI? Eleven letters, so \(11!\) if they were all different. But the four S's can be shuffled among themselves in \(4!\) ways without changing the word, likewise the four I's and the two P's. So \[\frac{11!}{4!\,4!\,2!} = \frac{39{,}916{,}800}{24 \cdot 24 \cdot 2} = 34{,}650.\] Count as if everything were different, then divide out the shuffles that change nothing.
Your turn
- Number plates have 3 letters then 3 digits. Assume 26 letters and 10 digits (0 through 9), with a leading zero allowed. How many are possible? How many if no letter and no digit may repeat?
- A poker hand is 5 cards from 52. How many hands are there? A flush is 5 cards all of one suit. How many flushes are there, and roughly what fraction of hands is that?
- Expand \((x+2)^5\) using the binomial theorem. Then find the coefficient of \(x^3\) in \((2x - 1)^7\) without expanding the whole thing.
- A city grid: you walk from \((0,0)\) to \((6,4)\) using only steps right (R) and up (U). How many routes? How many pass through \((2,2)\)?
One route: RRUURRURRU, ten steps of which four are U.
Stretch: a proof with no algebra
Prove by a counting story, not by factorials, that \(\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}\). (Think about whether one particular person is on the committee.) Then explain, the same way, why \(\binom{n}{0} + \binom{n}{1} + \cdots + \binom{n}{n} = 2^n\). Finally, find the first identity in the city grid: sort the routes to any point by whether their last step was R or U.
Answers
- \(26^3 \times 10^3 = 17{,}576{,}000\). Without repeats: \(26 \cdot 25 \cdot 24 \cdot 10 \cdot 9 \cdot 8 = 11{,}232{,}000\).
- \(\binom{52}{5} = 2{,}598{,}960\). Flushes: choose the suit (4), then 5 of its 13 cards: \(4\binom{13}{5} = 5148\). Fraction \(\approx 0.00198\), about 1 in 500. (This count includes the 40 straight flushes.)
- \((x+2)^5 = x^5 + 10x^4 + 40x^3 + 80x^2 + 80x + 32\) (coefficients \(\binom{5}{k}2^k\)). In \((2x-1)^7\) the \(x^3\) term is \(\binom{7}{3}(2x)^3(-1)^4 = 35 \cdot 8 = 280\).
- Ten steps, of which 4 are up: \(\binom{10}{4} = 210\). Through \((2,2)\): \(\binom{4}{2}\) routes to it, then \(\binom{6}{2}\) from it to \((6,4)\): \(6 \times 15 = 90\).
Stretch. Committees of \(k\) from \(n\) people: either Alice is on it (choose the other \(k-1\) from the remaining \(n-1\)) or she is not (choose all \(k\) from \(n-1\)). Every committee is exactly one of these, so the counts add. For the second: a subset of \(n\) people is formed by deciding in or out for each person, \(2^n\) ways; grouping subsets by size gives \(\sum_k \binom{n}{k}\). Same thing counted twice. On the grid, every route to \((r,u)\) arrives from \((r-1,u)\) or \((r,u-1)\), so the route counts obey the same addition rule as Pascal's triangle.