Permutations and Combinations

## The one question that decides it Every counting problem in this family reduces to a single test: **if I swap two of the things I picked, is that a different outcome?** - "Gold, silver, bronze from 10 runners" - swapping two medallists changes the result, so order matters. Count **permutations**. - "A 3-person committee from 10 people" - swapping two members changes nothing, so order does not matter. Count **combinations**. Everything else is bookkeeping. ## Factorials and the product rule `n!` ("n factorial") is `n x (n-1) x (n-2) x ... x 2 x 1`. So `5! = 120`. By convention `0! = 1`, because it is the empty product and because that convention is what makes the formulas below behave at their edges. The engine underneath is the **multiplication rule**: if a choice is made in stages and stage 1 has `a` outcomes, stage 2 has `b` outcomes for each of those, and so on, the total is `a x b x ...`. ## Permutations: n!/(n-k)! Arrange `k` of `n` distinct items in order. The first slot has `n` candidates, the second has `n-1` (one is used up), the third `n-2`, down to `n-k+1` for the last slot. Multiplying: ``` P(n, k) = n x (n-1) x ... x (n-k+1) = n!/(n-k)! ``` The `(n-k)!` in the denominator simply cancels the tail of `n!` you never used. Two edge cases fall out for free: `P(n, n) = n!/0! = n!` (arrange everything), and `P(n, 0) = 1` (there is exactly one way to arrange nothing). ## Combinations: divide out the orderings Now suppose only the *set* of chosen items matters. Each set of `k` items was counted once for every way of ordering it, and there are `k!` such orderings. So the ordered count overcounts by a factor of exactly `k!`: ``` C(n, k) = P(n, k)/k! = n!/(k!(n-k)!) ``` That single division is the whole difference between the two formulas. It is also the source of the most common error in interviews: dividing by `k!` in a problem where order genuinely does matter, or forgetting to divide when it does not. ## Useful properties - **Symmetry:** `C(n, k) = C(n, n-k)`. Choosing which `k` items to take is the same act as choosing which `n-k` items to leave behind, so the two counts must be equal. This is a bijection argument, not algebra, and interviewers like hearing it that way. It is also a computational shortcut: `C(50, 48)` is `C(50, 2) = 1225`. - **Boundaries:** `C(n, 0) = C(n, n) = 1`, and `C(n, 1) = n`. - **Pascal's rule:** `C(n, k) = C(n-1, k-1) + C(n-1, k)` - split on whether a particular item is in the group or not. ## Computing without exploding Never expand large factorials. Use the multiplicative form and cancel as you go: ``` C(52, 5) = (52 x 51 x 50 x 49 x 48)/(5 x 4 x 3 x 2 x 1) = 2,598,960 ``` That is the number of distinct 5-card hands from a standard 52-card deck, and it is the denominator of essentially every card-probability question. Because order does not matter in a hand, it is a combination. The numerator of such a question is usually a product of smaller combinations - for example, a full house is "pick the rank that appears three times (13 ways), pick 3 of its 4 suits, pick a different rank for the pair (12 ways), pick 2 of its 4 suits": `13 x C(4,3) x 12 x C(4,2) = 13 x 4 x 12 x 6 = 3744`. ## Where candidates go wrong 1. **Keying off the word "choose" in the prompt.** English is not the specification; the swap test is. 2. **Mixing the two inside one problem.** It is normal for a single count to use permutations at one stage and combinations at another - decide stage by stage. 3. **Double counting ranks.** In the full-house count, `13 x 12` is deliberately ordered (three-of-a-kind rank first, pair rank second) because those two roles are different. Using `C(13, 2)` there would halve the answer incorrectly. 4. **Assuming items are distinct.** Both formulas assume `n` distinguishable items drawn without repetition. Repeated letters or repeated draws need a different tool. ## The 15-second version Order matters: `n!/(n-k)!`. Order does not: divide that by `k!`. If you can state the swap test and then write both formulas, you have answered the question completely.