Exercises: Permutations and Combinations

These build from mechanical warm-ups through full combinatorial proofs, code, modeling, and feasibility judgments. Difficulty: ⭐ foundational, ⭐⭐ intermediate, ⭐⭐⭐ challenging. Worked solutions to the starred-with-a-dagger (†) and odd-numbered problems are in the appendix answers-to-selected.md; do them before you peek. For every count, the rubric rewards the same thing the chapter does: first classify the problem (order? repetition?), then name the model and apply it.

Part A — Warm-ups (⭐)

16.1 † Compute $P(7, 3)$ two ways: as a falling product $7 \times 6 \times 5$, and as $\frac{7!}{4!}$. Confirm they agree.

16.2 Compute $\binom{8}{3}$ and $\binom{8}{5}$. Without re-deriving, explain in one sentence why they are equal.

16.3 † How many distinguishable strings can be formed by rearranging the letters of BANANA? (Count the letters of each kind first.)

16.4 State the value of each, and the one-line reason: (a) $P(n, 0)$, (b) $\binom{n}{0}$, (c) $\binom{n}{n}$, (d) $P(n, 1)$.

16.5 † How many distinct ways can 6 distinct microservices be arranged in a circular dependency ring, where two arrangements are the same if one is a rotation of the other?

16.6 Write out row 6 of Pascal's triangle (the row $\binom{6}{0}, \dots, \binom{6}{6}$) using only row 5 ($1, 5, 10, 10, 5, 1$) and Pascal's rule — no factorials.

Part B — Computation & choosing the model (⭐⭐)

16.7 † For each scenario, state order? and repetition?, name the model, and give the count. (a) The number of 5-character API keys over a 62-symbol alphabet (A–Z, a–z, 0–9). (b) The number of ways to award 1st, 2nd, and 3rd place to 3 of 10 contestants. (c) The number of ways to choose 4 of 10 servers to receive a security patch (the chosen servers are interchangeable).

16.8 A team of 5 is chosen from 6 backend and 4 frontend engineers (10 total). How many teams contain at least one frontend engineer? Solve it by the subtraction rule, then check by a sum over cases.

16.9 † A standard 52-card deck. (a) How many 5-card hands are there? (b) How many 5-card hands consist entirely of hearts? (c) How many 5-card hands contain exactly two aces? (For (c): choose the aces, then choose the rest from the non-aces.)

16.10 Evaluate the coefficient of $x^3 y^4$ in $(x + y)^7$, and the coefficient of $x^2$ in $(2 + x)^5$. (For the second, match $(x + y)^n$ with $y = 2$, $n = 5$.)

16.11 † A password must be exactly 8 characters, chosen from the 26 lowercase letters, with no repeated letter. How many such passwords are there? State which model this is and why it is not $26^8$.

16.12 How many distinct anagrams of MISSISSIPPI place all four Ss together as a single block SSSS? (Treat the block as one super-letter and recount the multiset.)

Part C — Prove it (⭐⭐)

16.13 † (Scaffolded — fill in the missing steps.) Prove the absorption identity $\displaystyle r\binom{n}{r} = n\binom{n-1}{r-1}$ for $1 \le r \le n$, by an algebraic argument from the factorial formula. Fill the blanks:

• Start from the left: $r\binom{n}{r} = r \cdot \dfrac{n!}{r!\,(n-r)!}$. Cancel one factor of $r$ against $r! = r \cdot (r-1)!$ to get $r\binom{n}{r} = \dfrac{n!}{\underline{\hphantom{xxxx}}\;(n-r)!}$.
• Now pull one factor of $n$ out front using $n! = n \cdot (n-1)!$: $\dfrac{n!}{(r-1)!\,(n-r)!} = n \cdot \dfrac{(n-1)!}{(r-1)!\,(n-r)!}$.
• Recognize the remaining fraction as a binomial coefficient by checking its "bottom" sums to its "top": the lower indices are $(r-1)$ and $(n-r)$, which sum to $\underline{\hphantom{xxxx}}$, so the fraction is $\dbinom{\underline{\hphantom{xx}}}{\,r-1\,}$. Conclude $r\binom{n}{r} = n\binom{n-1}{r-1}$. $\blacksquare$

16.14 Prove $P(n, r) = r!\,\binom{n}{r}$ directly from the two factorial formulas (no story). Then state, in one sentence, the combinatorial reading of this identity that the chapter gave in §16.2.

16.15 † (Combinatorial proof.) Prove the hockey-stick identity: for $0 \le r \le n$, $$\sum_{i=r}^{n}\binom{i}{r} = \binom{n+1}{r+1}.$$ Strategy hint: count the $(r+1)$-subsets of $\{1, 2, \dots, n+1\}$ by classifying each subset by its largest element. (Pin down the set, then give both counts.)

16.16 (Combinatorial proof.) Prove Vandermonde's identity: for non-negative integers, $$\binom{m+n}{r} = \sum_{k=0}^{r}\binom{m}{k}\binom{n}{r-k}.$$ Strategy hint: a committee of $r$ is chosen from a group of $m$ women and $n$ men; split on how many of the $r$ are women.

16.17 † Give a combinatorial proof (not algebra) that $\displaystyle \binom{n}{k}\binom{k}{j} = \binom{n}{j}\binom{n-j}{k-j}$ for $j \le k \le n$. Hint: both sides count the ways to choose a $k$-member committee from $n$ people and then a $j$-member subcommittee from that committee.

Part D — Find the error (⭐⭐)

Each argument below is wrong. State precisely which step fails and why, and give the correct count.

16.18 † Claim: "The number of 5-card poker hands is $\binom{52}{1}\binom{51}{1}\binom{50}{1} \binom{49}{1}\binom{48}{1} = 52 \cdot 51 \cdot 50 \cdot 49 \cdot 48 = 311{,}875{,}200$." Find the flaw and give the correct count.

16.19 Claim: "A pizza shop has 8 toppings. The number of ways to choose a 3-topping pizza is $8 \times 8 \times 8 = 512$, since each of the 3 topping-slots can be any of the 8 toppings." Identify two distinct errors in this reasoning, and give the correct count (toppings cannot repeat, and order does not matter).

16.20 † Claim: "By the symmetry identity $\binom{n}{r} = \binom{n}{n-r}$, we have $\binom{10}{3} = \binom{10}{7}$, and therefore $P(10, 3) = P(10, 7)$ as well, since permutations are just ordered combinations." Find the false step. (Compute $P(10,3)$ and $P(10,7)$ to expose it.)

16.21 "Combinatorial proof" of $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$: "The right-hand side is a sum of two binomial coefficients, and binomial coefficients count subsets, so the right-hand side counts subsets; the left-hand side also counts subsets; therefore they are equal." Explain why this is not a valid combinatorial proof, and what is missing (recall the §16.5 pitfall).

Part E — Implement it (⭐⭐)

Write Python for each. Do not run it on the grader's machine — hand-trace and include an # Expected output: comment, matching the book's convention. Reference implementations are in code/exercise-solutions.py.

16.22 † Implement perm_count(n, r) as a falling product (do not build factorials and divide). Demonstrate it on perm_count(5, 3) and perm_count(6, 0), and state the expected output.

16.23 Implement comb_count(n, r) using the interleaved multiply-then-integer-divide pattern from §16.2, exploiting r = min(r, n - r). Demonstrate it on comb_count(10, 3) and comb_count(52, 5). In one comment line, explain why the integer division // never loses a remainder.

16.24 † Write pascal_row(n) that returns row $n$ of Pascal's triangle as a list, building each entry from the previous one (Pascal's "ratio" step, not the additive one). Print pascal_row(5) and the sum of its entries; state the expected output and what the sum equals in general.

16.25 Write a function multiset_perms(counts) that takes a list of multiplicities $[n_1, \dots, n_t]$ and returns the number of distinguishable arrangements $\frac{n!}{n_1!\cdots n_t!}$, where $n = \sum n_i$. Use math.factorial. Demonstrate it on the multiplicities of MISSISSIPPI.

Part F — Model it & Conjecture and test (⭐⭐⭐)

16.26 † (Model it.) A continuous-integration system runs a test suite that is a sequence of distinct stages. The team has 9 stages but can only fit 5 into the nightly window, and the order of the 5 stages matters (later stages depend on caches warmed by earlier ones). Translate "how many distinct nightly pipelines are possible?" into a precise counting model — state $n$, the number chosen, whether order matters, whether repetition is allowed — and give the count as a formula and a number. Then state how the count changes if the order suddenly does not matter, and by what factor.

16.27 (Model it.) A feature-flag system has 12 independent boolean flags. (a) Model "how many distinct configurations exist?" as a counting problem and give the count. (b) Model "how many configurations turn on exactly 3 flags?" and give the count. (c) Using the relationship between parts (a) and (b), state the identity that $\sum_{k=0}^{12}\binom{12}{k} = 2^{12}$ expresses about this flag system, in one plain-English sentence.

16.28 † (Conjecture and test, then prove.) Using your pascal_row from 16.24, compute the alternating sum $\sum_{k=0}^{n}(-1)^k\binom{n}{k}$ for $n = 1, 2, 3, 4, 5$. Conjecture the pattern. Then prove it from the binomial theorem (choose the right values of $x$ and $y$). What happens at $n = 0$, and why is that consistent?

16.29 (Conjecture and test, then prove.) For a fixed $n$, compute $\binom{n}{0}, \binom{n}{1}, \dots, \binom{n}{n}$ and find the value(s) of $k$ that **maximize** $\binom{n}{k}$, for several $n$ (both even and odd). Conjecture where the maximum sits. Then prove your conjecture by analyzing the ratio $\binom{n}{k+1} / \binom{n}{k}$ and finding where it crosses 1. (Hint: the ratio simplifies to $\frac{n-k}{k+1}$.)

16.30 † (Conjecture and test, then prove.) Conjecture a closed form for the number of lattice paths from $(0,0)$ to $(a, b)$ that move only right (R) or up (U) one unit at a time. Test by generating all such paths in code for small $(a, b)$ and counting them, comparing against your formula. Then prove the formula combinatorially (hint: a path is a string of R's and U's — how many of each, and how many distinguishable arrangements?).

Part G — Interleaved & Deep Dive

Mixing techniques from earlier chapters keeps them sharp.

16.31 † (Ch. 8 + 16.) Let $S$ be a set with $\lvert S \rvert = n$. (a) Using a Chapter 16 quantity, write the number of subsets of $S$ of size exactly $k$. (b) Sum over all $k$ to get the total number of subsets, and identify the resulting identity. (c) In Chapter 8 you proved $\lvert\mathcal{P}(S) \rvert = 2^n$ by an "in or out" argument; explain in one sentence why that argument and the sum in (b) are the same combinatorial proof seen from two angles.

16.32 (Ch. 15 + 16.) The combination formula $\binom{n}{r} = P(n,r)/r!$ is a direct application of one Chapter 15 rule. Name the rule, state what is being "divided out," and explain why the over-count is uniform (so the rule legitimately applies) — i.e., why every $r$-subset is counted exactly $r!$ times among the $r$-permutations.

16.33 † (Ch. 6 + 16.) Prove the binomial theorem $\displaystyle (x+y)^n = \sum_{k=0}^{n}\binom{n}{k}x^{n-k}y^k$ by **induction on $n$**, using Pascal's rule in the inductive step. (The chapter proved it combinatorially; this is the algebraic companion proof flagged in §16.4. Set up $P(n)$, do the base case $n = 0$, and in the step multiply the hypothesis by $(x + y)$ and collect like terms with Pascal's rule.)

16.34 (Ch. 11 + 16.) Using sigma notation (Chapter 11), write $P(n, r)$ as a product $\prod_{i=0}^{r-1}(n - i)$, and verify it equals $\frac{n!}{(n-r)!}$ for $r = 3$, $n = 6$ by expanding both. Then state, for fixed $r$, the degree of $P(n, r)$ as a polynomial in $n$ and the degree of $\binom{n}{r}$ as a polynomial in $n$ (they are the same — why?).

16.35 (Deep Dive — search-space feasibility.) A brute-force solver enumerates candidate solutions. For each task below, give the count, its growth class, and a one-sentence feasibility verdict at $10^9$ candidate-checks per second: (a) all subsets of 45 items; (b) all orderings of 14 items; (c) all 6-subsets of 60 items; (d) all length-12 strings over a 4-symbol alphabet (think DNA $k$-mers). For each, say whether brute force is feasible, borderline, or hopeless.

16.36 † (Deep Dive.) Prove combinatorially that $\displaystyle \sum_{k=0}^{n} k\binom{n}{k} = n\,2^{n-1}$. *Strategy:* count, two ways, the number of ways to choose a committee (of any size) from $n$ people and designate one member as its leader. (One side conditions on committee size and uses the absorption identity from 16.13; the other chooses the leader first.)

16.37 (Deep Dive — bridge to Chapter 17.) The fourth cell of the §16.3 decision table — "order does not matter, repetition allowed" — counts multiset selections as $\binom{n+r-1}{r}$. Without proving the formula (that is Chapter 17's "stars and bars"), verify it by hand for a tiny case: list all ways to choose $r = 2$ scoops from $n = 3$ flavors with repetition allowed, count them directly, and check the count equals $\binom{3 + 2 - 1}{2} = \binom{4}{2}$.

Solutions to † and odd-numbered exercises: see appendices/answers-to-selected.md. For each count, the rubric rewards: an explicit order?/repetition? classification, the named model, a correct application, and — for proofs — a single concrete set with both counts (or an explicit bijection) for the combinatorial arguments.