Further Reading: The Basics of Counting

Annotated pointers for going deeper into the counting rules. Start with the core textbook sections for more drill, then branch toward the CS applications (keyspaces, collisions, test coverage) or toward the deeper combinatorial theory (inclusion-exclusion in general, generating-function counting) as your interest pulls you.

Core textbook treatments

Rosen, Discrete Mathematics and Its Applications (8th ed.), §6.1 ("The Basics of Counting") and §8.5 (inclusion-exclusion) The market-standard treatment of the product and sum rules, the subtraction principle, and the division rule, with the largest well-graded exercise bank of any source here. §8.5 gives inclusion-exclusion for $n$ sets (which this chapter previews for two and three). If you want more mechanical practice than this chapter provides, start here.

Lehman, Leighton & Meyer, Mathematics for Computer Science (MIT 6.042J), the "Counting" chapters Freely available. The most CS-flavored presentation in print: counting is developed through the "bijection rule," the "division rule," and counting by mapping to known sets, with a strong emphasis on why each rule is valid — exactly the modeling discipline this chapter stresses. The treatment of the division rule and the generalized product rule pairs especially well with §15.5.

Graham, Knuth & Patashnik, Concrete Mathematics (2nd ed.), Chapter 4 (number theory) and Chapter 5 (binomial coefficients) Denser, but it shows counting as a working tool. Chapter 4's divisibility and floor-function material underpins the §15.4 "multiples of $d$ up to $N$" counts; Chapter 5 is the natural sequel once Chapter 16 introduces binomial coefficients. Save it for after you are comfortable with the basics.

On inclusion-exclusion and the division rule

Epp, Discrete Mathematics with Applications (5th ed.), the counting and inclusion-exclusion sections A gentler, example-rich careful treatment. If the partition-then-recombine proof of inclusion-exclusion in §15.4 felt fast, Epp's step-by-step Venn-diagram development is the standard "slow down and see it" companion.

Levin, Discrete Mathematics: An Open Introduction (3rd ed.), the "Counting" chapter (PIE section) Freely available. A clean, free treatment of the Principle of Inclusion-Exclusion with worked divisibility and "count the complement" examples that mirror §15.4 and §15.6 closely. An excellent no-cost place to find more two- and three-set problems.

On the CS applications (keyspaces, collisions, testing)

Katz & Lindell, Introduction to Modern Cryptography (3rd ed.), the chapters on security definitions and brute-force / exhaustive search The rigorous source behind §15.6's keyspace argument: how "the keyspace is size $K$" becomes a formal statement about an attacker's success probability and running time. Read it after Chapter 25 (RSA) for full payoff, but the framing of "search space size = security parameter" is already legible now.

Knuth, The Art of Computer Programming, Vol. 1: Fundamental Algorithms (3rd ed.), §1.2.5-§1.2.6 ("Permutations and Factorials," "Binomial Coefficients") The definitive reference for the descending product $n(n-1)\cdots(n-k+1)$ that §15.2 derived from the product rule, and where it is headed in Chapter 16. Authoritative and precise; use it as a lookup, not a first read.

Cormen, Leiserson, Rivest & Stein (CLRS), Introduction to Algorithms (4th ed.), the hashing chapter The reference for why counting the size of a hash function's output space matters: it is the denominator in every collision-probability argument (the count you set up in Exercise 15.24, made probabilistic in Chapter 17). Read alongside §15.6's state-space and keyspace material.

Suggested order

  1. Re-read §§15.2-15.6 here, then do Rosen §6.1 exercises for product/sum-rule drill and §8.5 for inclusion-exclusion.
  2. Read the MIT 6.042J counting chapters for the CS framing of the division and bijection rules.
  3. For more inclusion-exclusion and complement-counting practice, work the PIE section of Levin (free) or Epp.
  4. Skim the keyspace framing in Katz-Lindell and the hashing chapter of CLRS to see where §15.6 is headed (Chapters 17 and 25).
  5. Save Concrete Mathematics Chapters 4-5 and Knuth §1.2.5-6 for after Chapter 16 introduces permutations and binomial coefficients.