Further Reading: Advanced Counting

Annotated pointers for going deeper on the four tools of this chapter — pigeonhole, stars and bars, inclusion–exclusion, and generating functions. Start with the textbook sections that re-cover the material at a different angle, then branch toward whichever tool you want to push furthest. Generating functions in particular reward a second, more leisurely pass.

Core textbook treatments

Rosen, Discrete Mathematics and Its Applications (8th ed.), §6.2 (pigeonhole), §6.5 (combinations with repetition / stars and bars), §8.5–§8.6 (inclusion–exclusion and its applications), §8.4 (generating functions) The market-standard treatment, with a deep, well-graded exercise bank for every tool in this chapter. Its §8.6 works the derangement and "onto function" counts in full, parallel to §17.6; §8.4 is a gentle first pass at generating functions if ours moved quickly. The first place to go for more drill.

Lehman, Leighton & Meyer, Mathematics for Computer Science (MIT 6.042J), the "Counting" and "Generating Functions" chapters Freely available. The most CS-flavored presentation in print. The pigeonhole and counting chapters emphasize the bijection-and-mapping viewpoint we used for stars and bars, and the generating-functions chapter develops the "clothesline" picture with the same multiply-and-read-a-coefficient discipline as §17.5. The closest companion in spirit to this book.

Graham, Knuth & Patashnik, Concrete Mathematics (2nd ed.), Chapter 5 (binomial coefficients), Chapter 7 (generating functions), and the inclusion–exclusion material in Chapter 4–5 The deep end. Chapter 7 is, for many, the book on generating functions used as a working tool — it treats them as a notation you compute with, exactly the stance of §17.5, and goes vastly further (products, compositions, solving recurrences). Dense, but it rewards patience; save it for after you are comfortable with the chapter.

On generating functions specifically

Wilf, generatingfunctionology (3rd ed.) Freely available from the author's site. The source of the "a generating function is a clothesline on which we hang up a sequence of numbers for display" line quoted in §17.5. The definitive, friendly, book-length treatment; its first two chapters alone will deepen everything in §17.5, including why the formal-power-series view lets you ignore convergence.

Wilf, "The Snake Oil method," in generatingfunctionology Freely available. A short, delightful section showing generating functions evaluate sums and prove identities almost mechanically — a vivid demonstration of why packing a whole sequence into one object is so powerful. Read it once you can read off a coefficient comfortably.

On inclusion–exclusion and its classic applications

Rosen, Discrete Mathematics and Its Applications (8th ed.), §8.6 ("Applications of Inclusion–Exclusion") Works the derangement formula, the sieve-style "divisible by none of …" count, and the count of onto functions — the three applications behind §17.4 and §17.6 — with extra worked examples and the connection to the Euler $\phi$ function (a forward link to Part IV).

Levin, Discrete Mathematics: An Open Introduction (3rd ed.), the "Counting" chapter (PIE and stars-and-bars sections) Freely available. A clean, free re-derivation of stars and bars (with the same stars/bars diagram) and of inclusion–exclusion via complements — exactly the complement trick that powers the derangement and surjection counts. Good for a second explanation in different words.

Deeper dives and connections

Cormen, Leiserson, Rivest & Stein (CLRS), Introduction to Algorithms (4th ed.), the hashing chapter Connects the pigeonhole guarantee of §17.1 to real hash-table design — collision resolution, load factors, and why "more keys than slots" forces the chaining/open-addressing machinery. The natural bridge from this chapter's existence result to the engineering of Chapter 26.

Knuth, The Art of Computer Programming, Vol. 1 (3rd ed.), §1.2.6 (binomial coefficients) and the combinatorial identities The reference treatment of the binomial-coefficient algebra underlying stars and bars and the alternating sum $\sum_t (-1)^t\binom{s}{t} = 0$ that makes inclusion–exclusion work. Use it as a lookup when an identity in the exercises needs justifying.

Fun and intuition

"Derangements" and "Stirling numbers of the second kind" — entries in the OEIS (oeis.org, sequences A000166 and A008277) Free. The Online Encyclopedia of Integer Sequences entries for $D_n$ and for surjection-counts: dozens of identities, recurrences, and references, and a great source of "conjecture and test, then prove" material to extend Part F of the exercises.

3Blue1Brown, combinatorics and "$e$" explainers (YouTube) Free. Visual intuition for why $1/e$ appears in the hat-check problem (§17.6) and for binomial reasoning generally. Good for cementing the "why," especially the surprising emergence of $e$ from a purely combinatorial question.

Suggested order

  1. Re-read §§17.1–17.4 here, then do Rosen §6.2 and §6.5 exercises for pigeonhole and stars-and-bars drill.
  2. Read the MIT 6.042 counting chapter for the CS framing, and CLRS's hashing chapter to ground the pigeonhole-as-collision payoff before Chapter 26.
  3. Work Rosen §8.6 (or Levin's PIE section) for more derangement / onto-function practice.
  4. For generating functions, read §17.5 again slowly, then Wilf's generatingfunctionology Chapters 1–2; save Concrete Mathematics Chapter 7 for after Chapter 19, where generating functions solve recurrences in earnest.