Further Reading: Permutations and Combinations

Annotated pointers for going deeper. Start with the textbook sections to shore up the four models, then branch toward whichever pull you feel: the algebra of binomial coefficients, the art of combinatorial proof, or the algorithms that generate permutations and combinations in code.

Core textbook treatments

Rosen, Discrete Mathematics and Its Applications (8th ed.), §6.3–6.5 The market-standard development of permutations, combinations, the binomial theorem, and Pascal's identity, with a very large graded exercise bank. §6.3 is permutations/combinations; §6.4 is the binomial theorem and Pascal's triangle; §6.5 begins permutations and combinations with repetition (the fourth cell of our decision table, completed in Chapter 17). If you want more drill than this chapter provides, start here.

Lehman, Leighton & Meyer, Mathematics for Computer Science (MIT 6.042), the "Counting" chapters Freely available. The most CS-flavored treatment in print: it develops counting through the bijection rule and the division rule (our "overcount, then divide by the symmetry") and leans hard on combinatorial argument over formula-memorization — exactly the spirit of §16.5. Highly recommended as a companion.

Graham, Knuth & Patashnik, Concrete Mathematics (2nd ed.), Chapter 5 The definitive deep dive on binomial coefficients: dozens of identities, the absorption and symmetry rules, Vandermonde's convolution, and the "ten useful identities" every working combinatorialist knows. Dense and rewarding; treat it as the destination after this chapter, not the on-ramp. (Chapter 5 is the direct sequel to the binomial-coefficient material in §16.2 and §16.4.)

Levin, Discrete Mathematics: An Open Introduction (3rd ed.), the "Counting" chapter Freely available. A clean, undergraduate-friendly development of permutations, combinations, and the binomial theorem, with the permutations-vs-combinations decision spelled out and many small worked examples. A good free first re-read if any of §§16.1–16.3 needs reinforcement before you tackle Rosen's larger exercise set.

On combinatorial proof (the §16.5 technique)

Benjamin & Quinn, Proofs That Really Count: The Art of Combinatorial Proof (MAA) The single best book on double-counting and bijective proofs, written to be readable. It proves a huge catalogue of identities (including hockey-stick and Vandermonde, our Part C exercises) purely by counting a set two ways. If §16.5 was the most exciting part of the chapter for you, read this next. Pair it with the Part C exercises: try to find the book's proof of an identity before reading it.

Epp, Discrete Mathematics with Applications (5th ed.), the counting and combinatorics chapters A gentle, careful development with especially clear treatment of when order matters and the permutations-vs-combinations decision — the §16.3 skill. Good if the four-cell table still feels slippery and you want it re-explained from another angle with many worked examples.

Lehman, Leighton & Meyer, Mathematics for Computer Science (MIT 6.042), the "bijection rule" section Freely available. Worth a second mention specifically for its treatment of the bijection rule — counting a hard set by exhibiting a one-to-one correspondence with an easier one. This is the second flavor of combinatorial proof (alongside double counting) used in §16.5's symmetry argument, and 6.042 develops it with a string of memorable examples (lattice paths, balls-in-bins) that connect directly to our Part F lattice-path exercise.

On generating permutations and combinations in code

Knuth, The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, §7.2.1.2–§7.2.1.3 The authoritative reference on generating all permutations (§7.2.1.2) and all combinations (§7.2.1.3) — including the lexicographic "next combination" and "next permutation" algorithms our case study builds. Encyclopedic; consult the relevant section rather than reading cover to cover.

Cormen, Leiserson, Rivest & Stein (CLRS), Introduction to Algorithms (4th ed.), Appendix C The probability-and-counting appendix: a compact, rigorous restatement of permutations, combinations, and the binomial theorem in the notation algorithm analysis uses. The natural reference when these counts show up as the running time of an enumeration, which is the §16.6 connection.

Practice and problem banks

Rosen, Discrete Mathematics and Its Applications (8th ed.), end-of-section exercises for §6.3–6.5 The deepest well of graded drill problems for this chapter's material, from mechanical computation through interaction-heavy word problems and the standard identities. If the Part B and Part F exercises here left you wanting more reps on choosing the model (the §16.3 skill that most needs practice), Rosen's §6.3 set is where to get them; §6.4 drills the binomial theorem and Pascal's identity.

Epp, Discrete Mathematics with Applications (5th ed.), the combinatorics exercise sets Epp's problems lean toward careful, prose-heavy scenarios that force you to articulate why a problem is a permutation or a combination before computing — excellent rehearsal for the "state order? and repetition? first" discipline this chapter insists on. The worked examples that precede each set are unusually explicit about the classification step.

Tools and references

Python itertools documentation — permutations, combinations, combinations_with_replacement Free online. The standard-library implementations of all four cells of the §16.3 table. After building the generators from scratch (Project Checkpoint and case-study-02), read these docs to see the production versions and their lexicographic-order guarantees; the itertools recipes also show the iterative algorithms.

The On-Line Encyclopedia of Integer Sequences (OEIS), sequence A007318 (Pascal's triangle) Free online. The OEIS entry for the binomial coefficients read as a flat sequence, with a wealth of cross-references, identities, and appearances of $\binom{n}{k}$ across mathematics. A good source of "conjecture and test, then prove" material (Part F): pick any identity it lists and try to prove it combinatorially.

Going deeper

Graham, Knuth & Patashnik, Concrete Mathematics (2nd ed.), §5.1–5.2 on the binomial-coefficient identities and §5.3 on "generating functions" (preview) Once the basic identities of §16.4 are automatic, these sections show the machinery for discovering and proving identities in bulk — the absorption rule (our Exercise 16.13), the addition/summation formulas, and the first hints of generating functions, which Chapter 17 develops as "counting with algebra."

Knuth, The Art of Computer Programming, Vol. 4A, §7.2.1.3, on Gray codes and combination ranking For readers who enjoyed building the generators in case-study-02: this material covers ranking and unranking (mapping each combination to an integer index and back) and Gray-code orders that change one element at a time — the algorithms behind streaming through enormous combinatorial spaces without materializing them. Advanced, but the natural next step after next_combination.

Suggested order

  1. Re-read §§16.1–16.3 here, then do Rosen §6.3 exercises for drill on choosing the model.
  2. Read the MIT 6.042 counting chapters for the bijection/division-rule framing of §16.5.
  3. Skim CLRS Appendix C to see the counts in algorithm-analysis dress (pairs well with §16.6).
  4. For the proofs you enjoyed, read Benjamin & Quinn; for the algorithms, read Knuth Vol. 4A §7.2.1.3 and compare with the itertools docs.
  5. Save Concrete Mathematics Chapter 5 for a second pass, once the basic identities are automatic.