Exercises: Advanced Counting

These run from mechanical warm-ups through proofs, code, and modeling. Difficulty: ⭐ foundational, ⭐⭐ intermediate, ⭐⭐⭐ challenging. Worked solutions to the dagger (†) and odd-numbered problems are in the appendix answers-to-selected.md — attempt each one before you peek. For every count, name the tool and check its proviso (Is $n > m$? Are zeros allowed? Did you keep enough terms?); for every pigeonhole argument, state explicitly what the pigeons are and what the holes are.

Part A — Warm-ups (⭐)

17.1 † A company has 400 employees. Must two of them share a birthday (one of 366 possible days)? Identify the pigeons and the holes, and state the inequality that forces the conclusion.

17.2 Compute the guaranteed minimum for the fullest box in each case using $\left\lceil n/m\right\rceil$: (a) 50 files into 8 folders; (b) 1000 requests across 12 servers; (c) 17 pigeons into 5 holes.

17.3 † Write the integer equation that stars and bars solves for "distribute 9 identical stickers among 4 children, a child may get none," then compute the count.

17.4 How many non-negative integer solutions does $x_1 + x_2 + x_3 = 12$ have? Show the binomial coefficient before evaluating it.

17.5 † State the general inclusion–exclusion principle for three sets $A, B, C$, then say which single term disappears when you specialize it to two sets.

17.6 Compute the first six derangement numbers $D_0, D_1, \dots, D_5$ from the recurrence $D_n = (n-1)(D_{n-1} + D_{n-2})$ with $D_0 = 1$, $D_1 = 0$. Show each step.

Part B — Computation (⭐⭐)

17.7 † A bakery sells 5 kinds of muffin. You buy a box of 10, order irrelevant, repeats allowed. How many different boxes are possible? Identify $n$ (choices) and $k$ (types) before computing.

17.8 How many non-negative integer solutions does $x_1 + x_2 + x_3 + x_4 = 15$ have subject to $x_1 \ge 2$ and $x_2 \ge 3$? Substitute to remove the lower bounds, then apply stars and bars.

17.9 † How many integers in $\{1, 2, \dots, 600\}$ are divisible by at least one of $2$, $3$, or $7$? Use inclusion–exclusion, listing every floor you need. Then state how many are divisible by none of the three.

17.10 You roll 6 indistinguishable dice. How many distinct outcomes (multisets of face values) are there? Phrase it as "choose 6 from 6 types with repetition" and compute.

17.11 † Count the surjections from a 5-element set onto a 3-element set using $\sum_{j=0}^{m}(-1)^j\binom{m}{j}(m-j)^n$. Write out all four terms.

17.12 In the change example of §17.5, the generating function for pennies and nickels is $\frac{1}{1-x}\cdot\frac{1}{1-x^5}$. By hand, find the coefficient of $x^{12}$ — i.e. the number of ways to make 12¢ with pennies and nickels — by listing the legal (pennies, nickels) pairs.

17.13 † How many cards must you draw from a standard 52-card deck to guarantee at least 4 of the same suit? Use the generalized pigeonhole principle, and show why one fewer card is not enough.

Part C — Prove it (⭐⭐ / ⭐⭐⭐)

17.14 † (Scaffolded — fill the missing step.) Prove: among any 11 integers, some two have a difference divisible by 10. Complete the blanks. - Pigeons: the $\underline{\hphantom{xxxx}}$ chosen integers. - Holes: the $\underline{\hphantom{xxxx}}$ possible remainders when an integer is divided by 10, namely $\{0, 1, \dots, \underline{\hphantom{xx}}\}$. - Since $\underline{\hphantom{xx}} > \underline{\hphantom{xx}}$, the pigeonhole principle forces two integers $a, b$ into the same hole, so $a \equiv b \pmod{10}$, meaning $a - b = 10 \cdot \underline{\hphantom{xxxx}}$ for some integer, which is divisible by 10. $\blacksquare$

17.15 Prove the non-empty stars-and-bars formula: the number of solutions of $x_1 + \cdots + x_k = n$ with every $x_i \ge 1$ is $\binom{n-1}{k-1}$. (Strategy: substitute $y_i = x_i - 1$ and reduce to the non-negative case, citing §17.3.)

17.16 † Prove that in any group of 6 people, either 3 of them are mutual acquaintances or 3 are mutual strangers. (This is the friendship theorem $R(3,3) \le 6$. Strategy: fix one person $P$; among the other 5, by the generalized pigeonhole principle at least $\lceil 5/2\rceil = 3$ share one relation with $P$ — all acquaintances or all strangers. Then examine those three.)

17.17 Using the general inclusion–exclusion principle, prove the complement form: the number of elements of a finite universe $U$ that lie in none of $A_1, \dots, A_n$ is $$\lvert U\rvert - \sum_i \lvert A_i\rvert + \sum_{i

17.18 † (Deep Dive.) Prove the derangement recurrence $D_n = (n-1)(D_{n-1} + D_{n-2})$ combinatorially. (Strategy: in a derangement of $\{1, \dots, n\}$, consider where element $n$ goes — say position $i$, with $n-1$ choices — then split into the case where $i$ also maps to $n$ and the case where it does not. Match the two cases to $D_{n-2}$ and $D_{n-1}$.)

17.19 (Deep Dive.) Use the generating-function identity $\frac{1}{(1-x)^k} = \sum_{n\ge0} \binom{n+k-1}{k-1}x^n$ to give a second proof of stars and bars. Verify the coefficient formula by hand for $k = 2$ by expanding $\frac{1}{(1-x)^2}$ as the square of $\frac{1}{1-x}$ and reading off the coefficient of $x^n$.

Part D — Implement it (⭐⭐)

Write Python for each. Do not run it — hand-trace and include an # Expected output: comment, in the book's style. Build on math.comb where useful.

17.20 † Write min_to_guarantee(target, holes) returning the smallest number of objects that forces some hole to contain at least target objects (the inverse of the generalized pigeonhole bound). Test it on the "4 cards of one suit" problem (target=4, holes=4) and the "3 sharing a birth month" problem (target=3, holes=12).

17.21 Write solutions_with_floor(n, lowers) that counts non-negative integer solutions of $x_1 + \cdots + x_k = n$ where lowers[i] is the required minimum $x_i \ge \text{lowers[i]}$. (Hint: subtract sum(lowers) from $n$, then call a plain stars-and-bars count; guard against a negative remainder.) Trace it on Exercise 17.8.

17.22 † Write make_change_count(n, coins) that returns the number of ways to make n cents using the given coin denominations (order irrelevant), by multiplying the generating-function factors as coefficient lists (reuse the poly_mult idea from §17.5). Trace it for n=12, coins=[1, 5] and confirm it matches your hand answer to Exercise 17.12.

17.23 Write derangement_prob(n) returning $D_n / n!$ as a float, and print it for $n = 1$ through $8$. State which value it is converging to and how close $n = 8$ already is.

Part E — Find the error (⭐⭐)

Each "proof" or claim below is wrong. State precisely which step fails and why; give a counterexample or corrected count where appropriate.

17.24 † Claim: "I have 30 keys and a hash table of 30 slots, so by the pigeonhole principle two keys must collide." "Proof": there are 30 pigeons and 30 holes, so some hole gets two. — Find the flaw in this reasoning. Is the conclusion (a collision exists) even necessarily true?

17.25 Claim: the number of ways to give 8 identical candies to 3 children, each getting at least one, is $\binom{8+3-1}{3-1} = \binom{10}{2} = 45$. "Proof": stars and bars with $n = 8$, $k = 3$. — The setup ignored a constraint. State which formula should have been used and give the correct count.

17.26 † Claim: the number of integers in $\{1, \dots, 100\}$ divisible by 4 or 6 is $\lfloor 100/4\rfloor + \lfloor 100/6\rfloor = 25 + 16 = 41$. — Find the error in this inclusion–exclusion and give the correct value. (Hint: what is the right divisor for the overlap?)

17.27 Claim: "Surjections from a 4-set onto a 4-set number $4^4 - \binom41 3^4 = 256 - 4\cdot81 = -68$, which is absurd, so the surjection formula is broken." — The student stopped the alternating sum too early. Explain the error and compute the correct value.

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

17.28 † (Model it.) A content-delivery network must place $n$ identical cache copies of a video across $k$ distinct edge data centers; a data center may hold zero, one, or many copies. Engineering wants to know "how many distinct placement configurations exist" before deciding whether to enumerate them. Translate the scenario into a discrete-math object: name what plays the role of identical objects, what plays the role of distinct boxes, write the integer equation, and give the count formula. Then add the realistic constraint "every data center must hold at least one copy for redundancy" and restate the count.

17.29 (Model it.) A "secret santa" draw assigns each of $n$ coworkers a giftee; nobody may draw their own name. Model "a valid draw" as a discrete-math object from this chapter, state which count gives the number of valid draws, and explain in one sentence why the probability that a random assignment is valid is close to $1/e$ once $n$ is moderately large.

17.30 † (Conjecture and test, then prove.) Let $f(k)$ be the number of non-negative integer solutions of $x_1 + x_2 = k$. Compute $f(0), f(1), \dots, f(5)$ by hand (or with your code from Part D), conjecture a closed form $f(k) = \underline{\hphantom{xxxx}}$, then prove it from stars and bars. What familiar sequence is $f$?

17.31 (Conjecture and test.) Investigate the ratio $D_n / D_{n-1}$ for $n = 2, 3, \dots, 8$ using the recurrence. Conjecture what it is approaching as $n$ grows, and connect your answer to the fact that $D_n \approx n!/e$. (You do not need a full proof — report the pattern and the heuristic.)

Part G — Interleaved & Deep Dive

Mixing techniques from earlier chapters keeps them sharp.

17.32 † (Ch. 16 + 17.) The inclusion–exclusion proof of §17.4 turned on $\sum_{t=0}^{s}(-1)^t\binom{s}{t} = 0$. Derive this directly from the binomial theorem (Ch. 16) by choosing the right values of $x$ and $y$ in $(x+y)^s = \sum_t \binom{s}{t}x^t y^{s-t}$, and then explain in one sentence how subtracting the $t = 0$ term yields the "counted exactly once" conclusion.

17.33 (Ch. 15 + 17.) Counting all functions from an $n$-set to an $m$-set gives $m^n$ by the product rule (Ch. 15) — the $j = 0$ term of the surjection formula. Explain, using the product rule, why "functions that miss a fixed set of $j$ targets" number exactly $(m-j)^n$, and why there are $\binom{m}{j}$ such sets.

17.34 † (Ch. 16 + 17.) Show that the two stars-and-bars forms $\binom{n+k-1}{k-1}$ and $\binom{n+k-1}{n}$ are equal, citing the symmetry identity $\binom{a}{b} = \binom{a}{a-b}$ from Chapter 16. Then interpret each form combinatorially (choosing bar positions vs. choosing star positions).

17.35 (Ch. 9 + 17.) The pigeonhole principle can be stated as "a function $f\colon A \to B$ with $\lvert A\rvert > \lvert B\rvert$ is not injective" (injectivity defined in Chapter 9). Prove the contrapositive direction is what hashing needs: if $K$ is infinite and $m$ is finite, then no $h\colon K \to \{0, \dots, m-1\}$ is injective — so a collision is unavoidable. (One short paragraph.)

17.36 (Deep Dive — preview of Ch. 18.) §17.5 promised that generating functions solve recurrences. As a warm-up, write the generating function $A(x) = \sum_{n\ge0} a_n x^n$ for the sequence defined by $a_0 = 1$ and $a_n = 2a_{n-1}$ for $n \ge 1$. Manipulate $A(x)$ algebraically to a closed form, and read off $a_n$. (You will recognize the answer; the method is what Chapter 18–19 generalize.)

Solutions to † and odd-numbered exercises: see appendices/answers-to-selected.md. For each count the rubric rewards: naming the tool, checking its proviso (the inequality $n>m$; whether zeros are allowed; the correct overlap divisor; the right sign on each intersection term), and a clean final number.