Chapter 16 — Key Takeaways
Permutations and Combinations: Arranging and Choosing. One-page review card. Reread before the exam.
The two questions that pick the model
Ask them in order; the pair selects a cell.
- Does order matter? Reordering the chosen items → a different outcome you count separately? - Yes → permutation. No → combination.
- Is repetition allowed? Can the same item be chosen more than once?
| Order matters | Order does NOT matter | |
|---|---|---|
| No repetition | $r$-permutation: $P(n,r)=\dfrac{n!}{(n-r)!}$ | $r$-combination: $\dbinom{n}{r}=\dfrac{n!}{r!\,(n-r)!}$ |
| Repetition allowed | sequences: $n^r$ | multiset: $\dbinom{n+r-1}{r}$ (Ch. 17) |
Tells: "assign to distinct roles / ranked / slots" → order matters. "committee / hand / subset / set of" → order does not. "password / PIN / string / array of values" → repetition allowed.
Formula sheet
| Quantity | Formula | Notes |
|---|---|---|
| Factorial | $n! = n(n-1)\cdots 1$, $\;0!=1$ | $0!=1$ makes the rest consistent |
| Permutations of all $n$ | $P(n,n)=n!$ | a full lineup |
| $r$-permutations | $P(n,r)=\dfrac{n!}{(n-r)!}=n(n-1)\cdots(n-r+1)$ | $r$ falling factors |
| Multiset permutations | $\dfrac{n!}{n_1!\,n_2!\cdots n_t!}$ | $n_1+\cdots+n_t=n$ (e.g. MISSISSIPPI $=34{,}650$) |
| Circular arrangements | $(n-1)!$ | $n!$ ÷ $n$ rotations |
| Combinations | $\dbinom{n}{r}=\dfrac{P(n,r)}{r!}=\dfrac{n!}{r!\,(n-r)!}$ | unordered = ordered ÷ $r!$ |
| Perm–comb relation | $P(n,r)=r!\dbinom{n}{r}$ | they differ by exactly $r!$ |
| Edge cases | $\dbinom{n}{0}=\dbinom{n}{n}=1$, $\;\dbinom{n}{1}=n$ | choose nothing / all / one |
Key identities
| Identity | Statement | Why (one line) |
|---|---|---|
| Symmetry | $\dbinom{n}{r}=\dbinom{n}{n-r}$ | choosing who's in = choosing who's out (complement bijection) |
| Pascal's rule | $\dbinom{n}{k}=\dbinom{n-1}{k-1}+\dbinom{n-1}{k}$ | split $k$-subsets on whether they contain a fixed element |
| Binomial theorem | $(x+y)^n=\sum_{k=0}^{n}\dbinom{n}{k}x^{n-k}y^{k}$ | $\binom{n}{k}$ = ways to pick which $k$ factors give a $y$ |
| Total subsets | $\sum_{k=0}^{n}\dbinom{n}{k}=2^n$ | set $x=y=1$; or: 2 choices per element |
| Alternating sum | $\sum_{k=0}^{n}(-1)^k\dbinom{n}{k}=0$ $(n\ge1)$ | set $x=1,y=-1$; #even-subsets = #odd-subsets |
| Committee–chair | $k\dbinom{n}{k}=n\dbinom{n-1}{k-1}$ | count (committee, chair) two ways |
Pascal's triangle (row $n$ = the $\binom{n}{k}$): each interior entry = sum of the two above; row sums $= 2^n$.
1 / 1 1 / 1 2 1 / 1 3 3 1 / 1 4 6 4 1 / 1 5 10 10 5 1
Combinatorial (double-counting) proof — the recipe
To prove $A = B$ combinatorially:
- Name one concrete finite set $S$.
- Show $A$ counts $S$ correctly (no omissions, no duplicates).
- Show $B$ counts the same $S$ correctly (a different way) — or biject $S$ with a set of size $B$.
- Conclude $A=B$ (a finite set has exactly one size).
It is a real proof because counting is single-valued. A "proof" that only describes one side is not a proof.
Search-space sizes (feasibility verdicts)
| Algorithm enumerates… | Count | Growth | Brute force OK to ~ |
|---|---|---|---|
| all subsets (include/exclude each) | $2^n$ | exponential | $n\approx 30$ |
| all $k$-subsets ($k$ fixed) | $\dbinom{n}{k}=\Theta(n^k)$ | polynomial | large $n$ (poly) |
| all orderings | $n!$ | super-exponential | $n\approx 12$ |
| length-$r$ strings over $n$ symbols | $n^r$ | exponential in $r$ | small $r$ |
Rule of thumb at $10^9$ ops/s: $2^{30}\approx$ 1 s, $2^{40}\approx$ 18 min, $2^{50}\approx$ 13 days; $13!\approx$ 6 s, $20!\approx$ decades. Every +10 to $n$ multiplies $2^n$ work by ~1000.
Decision aid: "which number do I compute?"
- Counting arrangements / lineups / assignments to distinct slots → $P(n,r)$ (or $n!$ if $r=n$).
- Counting subsets / committees / hands → $\dbinom{n}{r}$.
- Counting strings / PINs / arrays (repeats allowed, order matters) → $n^r$.
- "At least one" constraint → count all, subtract the violators (subtraction rule).
- Disjoint groups, pick from each → multiply the per-group $\binom{}{}$ (product rule).
- Mutually exclusive cases → add the per-case counts (sum rule).
Common pitfalls
| Pitfall | Fix |
|---|---|
| Using $P(n,r)$ where the problem wants $\binom{n}{r}$ (the poker-hand error) | Ask: does reordering the chosen items make a new outcome? If no, divide by $r!$. |
| Forgetting to divide out repeats in multiset permutations | $n!$ ÷ ($n_1!\,n_2!\cdots$) for each repeated group. |
Computing $\binom{n}{r}$ as factorial(n)//factorial(r)//factorial(n-r) |
Use the interleaved falling product; never form giant factorials. |
| Combinatorial proof that only explains one side | Pin down one set; argue both counts are correct. |
| Assuming brute force "will be fine" | Compute $2^n$ / $n!$ first; it is usually the deciding number. |
Toolkit additions (dmtoolkit/combinatorics.py)
| Function | Returns | Idea |
|---|---|---|
perm_count(n, r) |
$P(n,r)$ | falling product $n(n-1)\cdots(n-r+1)$ |
comb_count(n, r) |
$\binom{n}{r}$ | symmetry to shrink $r$, then interleaved multiply / // |
permutations(it, k) |
yields $k$-permutations | recurse on pool[:i]+pool[i+1:] (revisits in new orders) |
combinations(it, k) |
yields $k$-combinations | recurse on pool[i+1:] only (never reorders) |
Sanity invariant: len(list(permutations(s,k))) == perm_count(len(s),k) and
len(list(combinations(s,k))) == comb_count(len(s),k). The one-line difference
pool[:i]+pool[i+1:] vs. pool[i+1:] is the permutation-vs-combination distinction in code.
The one move to remember
Overcount on purpose, then divide by the symmetry you're ignoring. $P(n,r)\div r! = \binom{n}{r}$ · $n!\div(n_1!n_2!\cdots)=$ multiset perms · $n!\div n=(n-1)!$ circular.