Part III: Counting and Probability
"The art of counting is the art of not listing." — a teaching maxim of combinatorics
Every program lives inside a space of possibilities, and almost every interesting question about a program is really a question about the size of that space. How many passwords must an attacker try before one works? How many states can your protocol be in, and have you tested all of them? How many comparisons does merge sort make on a million-element array? How full does the busiest bucket in your hash table get, and will it stay fast? These look like four unrelated engineering worries. They are, in fact, four faces of two skills: counting the outcomes of a process, and reasoning about how likely each outcome is. Part III builds both.
The two skills are deeply linked, and the link is almost embarrassingly direct. Counting answers "how many?"; probability answers "how likely?"; and when outcomes are equally likely, a probability is just a count of favorable outcomes divided by a count of all outcomes — two numbers combinatorics already taught you to find. So we develop them together, counting first and probability second, and you will see the second half repaying the first on nearly every page. Along the way these tools stop feeling like puzzles and start feeling like instruments: a brute-force attack becomes a multiplication, an "unavoidable" hash collision becomes the pigeonhole principle, the running time of a recursive function becomes a recurrence you can solve, and the question "is this randomized algorithm probably correct?" becomes a number you can actually compute.
This is also where the book's analytical machinery becomes genuinely useful rather than merely rigorous. Part I gave you proof; Part II gave you the objects — sets, functions, relations — and the language of asymptotics. Part III turns that foundation toward the questions practitioners ask out loud: How big? How fast? How likely? The recurring theme that computation and proof are complementary reaches full strength here. You will write Python that estimates a probability over a million simulated trials — cheap, approximate, fallible — and then prove the exact value by hand — expensive, certain — and you will learn precisely when each is the right tool. By the end you will count things you could never list, and you will reason honestly about uncertainty instead of guessing.
What You Will Learn
Chapter 15 — The Basics of Counting. The four rules everything else rests on: multiply for a sequence of independent choices (the product rule), add over disjoint cases (the sum rule), subtract the overlap so you do not double-count (inclusion–exclusion for two and three sets), and divide out a fixed over-count (the division rule). The hard part is never the arithmetic; it is the modeling — deciding which rule a problem calls for — and you will practice it on real input spaces and password keyspaces.
Chapter 16 — Permutations and Combinations. When order matters you have a permutation, $P(n,k)$; when it does not you have a combination, $\binom{n}{k}$. You will learn to choose the right model, prove identities by combinatorial argument (counting one set two ways) rather than algebra, and meet the binomial theorem and Pascal's triangle. The CS payoff is sizing search spaces: exactly how many subsets, orderings, or candidate solutions a brute-force algorithm must sift through.
Chapter 17 — Advanced Counting. Four sharper tools. The pigeonhole principle — if $n+1$ items go into $n$ boxes, some box holds two — proves, among other things, that hash collisions are mathematically unavoidable. Stars and bars counts distributions of identical items; general inclusion–exclusion extends Chapter 15's overlap correction to any number of sets; and generating functions turn counting problems into algebra you can manipulate. Applications include derangements and surjection counts.
Chapter 18 — Recurrence Relations. A recursive function defines its own cost recursively, and that cost is a recurrence. You will learn to model problems this way (Tower of Hanoi, tilings), classify the recurrences you meet, and solve linear homogeneous ones exactly via the characteristic equation. This is where Fibonacci's recurrence gets pinned down precisely — and where you start reading a recurrence straight off a block of recursive code.
Chapter 19 — Solving Recurrence Relations. The divide-and-conquer toolkit. The recursion-tree method makes a recurrence visible; the Master Theorem solves the common cases at a glance; and with them you will analyze merge sort and binary search from first principles. The chapter delivers the Fibonacci payoff promised since Chapter 6: a closed form via the golden ratio, and an $O(\log n)$ algorithm using matrix exponentiation.
Chapter 20 — Discrete Probability. Counting becomes probability. You will build a probability space (a sample space with probabilities summing to 1), treat events as subsets, and define random variables as functions on outcomes. The centerpiece is expected value and its astonishing linearity, which cracks problems that brute force cannot — plus variance, and the probabilistic method, a proof technique that shows an object exists by showing a random one works with positive probability.
Chapter 21 — Conditional Probability and Bayes' Theorem. How evidence should update belief. You will compute conditional probabilities, reason carefully about independence, and apply Bayes' theorem — then watch it expose the base-rate fallacy, the reasoning error behind misread medical tests and false-alarm-prone alerts. The chapter cashes this out in two CS applications: a naive Bayes spam classifier and an analysis of why randomized algorithms work.
How This Part Fits
Part III stands on the two parts before it. Counting is applied set theory: the product and sum rules are statements about Cartesian products and disjoint unions from Chapter 8, and the division rule leans on the equivalence classes of Chapter 12. Permutations and combinations formalize the factorial first met in Chapter 11. Recurrences are the analytic continuation of the induction and recursive definitions of Chapters 6 and 7 and the sequences of Chapter 11, and they are scored with the Big-O language of Chapter 14 — which is exactly why Chapter 19 lists Chapter 14 as a prerequisite. Probability, finally, is built directly on the counting of Chapters 15 and 16: an equally-likely probability is a ratio of two counts.
Looking forward, this part loads the springboard for the rest of the book. The keyspace sizing of Chapter 15 and the pigeonhole argument of Chapter 17 return in Part IV: keyspace sizing frames why RSA is hard to break (Chapter 25), and pigeonhole explains why every hash function collides (Chapter 26). The recurrence-solving of Chapter 19 underwrites the algorithm analysis running through Part V's graph algorithms and resurfaces in the complexity theory of Chapter 37. And probability is not a detour but a permanent addition to your toolkit: the probabilistic method previewed in Chapter 20 reappears in Chapter 40, and Bayesian reasoning from Chapter 21 is the conceptual root of the machine-learning systems these foundations ultimately support. In the Discrete Math Toolkit, this part contributes three modules — combinatorics.py (Chapters 15–17), recurrences.py (Chapters 18–19, including the $O(\log n)$ fib), and probability.py (Chapters 20–21) — each tested on many cases in code and justified by proof.
Time Investment
| Chapter | Title | Estimated time |
|---|---|---|
| 15 | The Basics of Counting | 5–6 hours |
| 16 | Permutations and Combinations | 6–7 hours |
| 17 | Advanced Counting | 7 hours |
| 18 | Recurrence Relations | 6–7 hours |
| 19 | Solving Recurrence Relations | 7 hours |
| 20 | Discrete Probability | 6–7 hours |
| 21 | Conditional Probability and Bayes' Theorem | 6–7 hours |
| Part III total | ≈ 44–48 hours |
These are honest estimates for a reader who works the exercises rather than only reading them — and in this part, the exercises are the learning. Counting cannot be absorbed by watching; it is a skill you build by modeling problems and checking your count against a small brute-force enumeration. Budget the time, keep a Python REPL open to test your reasoning on tiny cases, and you will finish able to size, time, and reason about the possibility spaces your programs inhabit.
We begin where every counting argument begins: with the deceptively simple decision of when to multiply and when to add. Chapter 15 makes those rules precise, shows why getting the model wrong can put your answer off by orders of magnitude, and turns the size of a possibility space into something you can compute on the back of an envelope. Turn the page and start counting — without listing.