Combinatorics

Mental model

Every counting problem is a question about whether order matters and whether repetition is allowed; get those two right and the formula follows. Inclusion-exclusion exists because naive addition double-counts overlaps, and the pigeonhole principle is the one tool that proves something must exist without constructing it — which is why it shows up in hash-collision and cache arguments rather than in counting exercises.

How to study Combinatorics

Begin by restating the mental model in your own words, then connect it to a concrete system you have built or operated. Name the mechanism, the constraint it addresses, and the trade-off it introduces. Use the linked roadmap and primary implementation references to check details, but close the source before writing your explanation. Retrieval is the learning step; rereading is only preparation.

Next, compare Combinatorics with Queueing Theory, 1D DP. Ask what changes in correctness, latency, resource use, operability, and failure recovery. Complete Count with inclusion-exclusion and preserve the command, input, output, and one failed attempt as evidence. Finish by explaining the idea without jargon to someone who has not studied the track.

Proof of understanding

• Explain the mechanism from first principles and identify the state it reads or changes.
• Give one situation where the concept is the right choice and one where it is not.
• Predict a realistic failure mode before running the drill, then compare the prediction with evidence.
• Connect the result to a roadmap or build artifact instead of treating the concept as isolated trivia.

Where it matters

Collision probability, birthday-paradox reasoning about id spaces, and the state-space estimates behind DP problems.

Common mistakes

• Using a permutation where order does not matter, inflating the count by k!
• Adding the sizes of overlapping sets without subtracting the intersection
• Treating 'at least one' directly instead of counting the complement, which is usually far easier
• Assuming outcomes are equally likely when the sample space was constructed unevenly

Learn from primary sources

Use the linked roadmap context and practice prompt.

Practice and explain it back

Review prompts

• 'At least one collision among k hashed items' is awkward to count directly. What is the standard move, and why is it easier?

Build evidence

Use a roadmap capstone to turn this concept into working evidence.

Learning paths

• 12-Week Active Math Stack
• 30-Day Probability & Statistics