In counting problems, how do you decide between n^k, n!/(n-k)! and n choose k?

## Two questions, four formulas Before writing anything down, answer two independent yes/no questions about the problem. 1. **Does order matter?** If rearranging what you picked produces a different outcome, order matters. 2. **Can the same item be picked more than once?** Drawing *with replacement* (put it back, it can come again) allows repeats; drawing *without replacement* (each item is used up) does not. Those two answers land you in exactly one of four cells, each with its own formula for choosing `k` things from `n`: | | Order matters | Order does not matter | |---|---|---| | **With replacement** | `n^k` | `C(n+k-1, k)` | | **Without replacement** | `n!/(n-k)!` | `C(n, k)` | ## Cell 1: ordered, with replacement - n^k Each of the `k` slots is filled independently from the full pool of `n`, so the multiplication rule gives `n x n x ... x n = n^k`. This is the password and PIN cell. An 8-character password over the 62 symbols `a-z`, `A-Z`, `0-9` has `62^8 = 218,340,105,584,896` possibilities, roughly 2.18 x 10^14. A 4-digit PIN has `10^4 = 10,000`. Note that `n^k` grows in the *exponent of length*, which is why adding one character multiplies the space by `n` while adding one symbol to the alphabet barely moves it. ## Cell 2: ordered, without replacement - n!/(n-k)! Each pick removes an item from the pool: `n x (n-1) x ... x (n-k+1)`, which is `n!/(n-k)!`. A licence plate of 3 letters followed by 3 digits, with repeats forbidden, is `(26 x 25 x 24) x (10 x 9 x 8) = 15,600 x 720 = 11,232,000`. Allowing repeats moves you to cell 1: `26^3 x 10^3 = 17,576,000`. The no-repeat rule costs about 36 percent of the space here - worth noticing, because a "no repeated characters" password policy shrinks the search space rather than growing it. ## Cell 3: unordered, without replacement - C(n, k) The ordered count over-counts each selected group once per arrangement, and each group has `k!` arrangements, so `C(n, k) = n!/(k!(n-k)!)`. Choosing 3 of 26 letters as a set, ignoring order, is `C(26, 3) = 2600`, far smaller than the 15,600 ordered strings. ## Cell 4: unordered, with replacement - C(n+k-1, k) This is the cell candidates skip, and it is worth being able to name. Picking `k` items from `n` *types*, where you may take a type more than once and only the multiset of types matters, gives `C(n+k-1, k)`. Choosing 3 scoops from 5 flavours, repeats allowed and scoop order irrelevant, is `C(7, 3) = 35`. A warning that separates strong answers from weak ones: the `C(n+k-1, k)` outcomes in this cell are **not equally likely**. Two chocolate scoops and one vanilla can arise in three orderings while three chocolates arise in one, so if you are computing a probability you must work in the ordered cell where outcomes *are* equally likely, then aggregate. Cell 4 is a counting answer, not a probability model. ## Sanity checks that catch mistakes - **Ordering the four counts.** For fixed `n` and `k` with `k <= n`, the ordered-with-replacement count is the largest and the unordered-without-replacement count is the smallest. If your "unordered" answer exceeds your "ordered" answer, you have made an error. - **Try k = 1.** All four formulas must collapse to `n`. `n^1 = n`, `n!/(n-1)! = n`, `C(n,1) = n`, `C(n, 1) = n`. A formula that fails this is mis-transcribed. - **Try tiny numbers you can enumerate.** With `n = 2`, `k = 2`: ordered with replacement is 4 (AA, AB, BA, BB), ordered without is 2 (AB, BA), unordered without is 1 (the set {A,B}), unordered with is 3 ({A,A}, {A,B}, {B,B}). Every formula reproduces these. ## Common failure modes 1. **Using `n^k` when the pool is consumed.** Dealing cards from one deck, seating distinct guests, or assigning distinct roles all remove the item from play. 2. **Dividing by `k!` reflexively.** If the slots are distinguishable - first place, last four digits, the middle letter - order matters and the division is wrong. 3. **Conflating "without replacement" with "unordered".** They are independent axes. Ordered without replacement is a perfectly ordinary cell. 4. **Ignoring per-position alphabets.** A plate whose letters and digits come from different pools multiplies the two counts; it is not one uniform `n^k`. ## The compact answer Say the two questions out loud, name the cell, then write the formula. That sequence is what an interviewer is listening for - the formulas themselves are the easy part.