Factorials & Combinations

## The one test that decides it Every problem in this family reduces to a single question: **if I swap two of the chosen items, do I have a different outcome?** If yes, the arrangement itself is part of the answer and you are counting *permutations*. If no — the outcome is nothing more than *which* items were chosen — you are counting *combinations*. A *permutation* of size k drawn from n distinct items is an ordered sequence of k of them, no item used twice. A *combination* of size k is an unordered set of k of them. Same raw material, different notion of "same outcome". ## Working a concrete count Thirty entrants; the leaderboard awards a distinct first, second and third place. Fill the slots one at a time. Any of the 30 can take first place. Whoever takes it is gone, so 29 remain for second, and 28 for third. Multiply the independent slot choices: `P(30,3) = 30 x 29 x 28 = 24,360` Now change the question: pick three finalists, no ranking. Take the 24,360 ordered lineups and group them by *which trio* they contain. Each trio of three distinct entrants appears in exactly `3! = 6` different orders, so every group has exactly six members. The number of groups is therefore `C(30,3) = 24,360 / 6 = 4,060` That grouping argument — a clean many-to-one correspondence with a constant group size — is the entire reason the `k!` divisor appears. It is worth being able to say out loud, because it generalises: whenever you have counted ordered outcomes but the order is not meaningful, divide by the number of orderings of each outcome. ## The formulas, and where they come from - `P(n,k) = n x (n-1) x ... x (n-k+1) = n! / (n-k)!` — the falling product of k factors, written as a ratio of factorials. - `C(n,k) = P(n,k) / k! = n! / (k! (n-k)!)`. The factorial forms are the compact way to *write* these counts, not the sensible way to *evaluate* them: for the podium, `30!` is a 33-digit number even though the answer is 24,360. When you actually compute, use the falling product, or the running multiply-and-divide form of the binomial coefficient. ## Two assumptions people silently conflate Order-matters is only one of the two switches. The other is whether an item may be reused. | | order matters | order ignored | |---|---|---| | **each item used at most once** | `P(n,k) = n!/(n-k)!` — 24,360 | `C(n,k) = n!/(k!(n-k)!)` — 4,060 | | **items may repeat** | `n^k` — 27,000 | a separate counting family, not covered here | Most real miscounts are not arithmetic errors; they are an unstated assumption. "Three podium places from thirty entrants" is 24,360 only if one entrant cannot occupy two places. If the scenario were three awards that the same entrant *could* sweep, the count is `30^3 = 27,000`. Say both assumptions aloud before you write a formula. ## The symmetry worth knowing `C(n,k) = C(n, n-k)`. Choosing which 3 entrants make the shortlist is the same act as choosing which 27 do not, so the counts must be equal: `C(30,3) = C(30,27) = 4,060`. This is not a curiosity — it is the practical trick that lets you always compute with the smaller of k and n-k, keeping loop lengths and intermediate values small. ## Why an interviewer bothers asking Because the distinction sets the *size of a space someone is about to search*. Selections and arrangements of the same items are not close in magnitude; the ratio between them is `k!`, and `k!` outruns any constant factor an engineer can win back by optimising a loop. Getting the count right on paper decides whether an exhaustive approach is even on the table, before a line of code exists. ## Wrong turns to avoid - Reaching for `n!` when only k of the n items are chosen. `30!` counts orderings of *all thirty* entrants, roughly 2.65 x 10^32 — a different question entirely. - Assuming combinations are larger than permutations. For `k >= 2` the combination count is strictly smaller; the two coincide only when `k` is 0 or 1. - Treating "distinct items" and "order matters" as the same switch. They are independent, and each has its own formula.