Combinatorics & Counting
The problem
‘How many possibilities are there?’ decides whether an approach is feasible: how many test cases cover the input space, how many states a system can reach, how big a search space an algorithm faces. Counting turns these from guesses into calculations.
Why now
Sets tell us what the space of possibilities is, but not its size when the space is built combinatorially (choices multiply, orderings explode). Enumerating by hand fails immediately — 10 boolean feature flags already give 1024 configurations.
Mental model
All of counting is two moves: multiply independent choices, add mutually exclusive cases — then correct for overcounting (divide out orderings, subtract overlaps). Permutations, combinations, and the inclusion–exclusion principle are these moves packaged.
Requires
- Sets & LogicMathematical Thinking
Counting is measuring the size of a set; sum and product rules are statements about unions and Cartesian products of sets, and inclusion–exclusion is literally set algebra.
Helps
- Functions & RelationsMathematical Thinking
The cleanest counting arguments work by exhibiting a bijection ('count something easier that corresponds one-to-one'); bijections are functions, so the vocabulary helps — but basic counting works without it.
Unlocks
Related
Used in
- Big-O analysis (counting operations an algorithm performs)
- Estimating state-space size: feature-flag combinations, retry × timeout × region matrices
- Hash-collision probability and the birthday bound
- Combinatorial test design (pairwise testing)
Projects
- Compute the number of distinct configurations of a real config file in one of your projects; decide whether exhaustive testing is feasible
- Simulate the birthday paradox and compare the empirical collision rate to the calculated one
Examples
- 4 environments × 3 regions × 2 tiers = 24 deployment targets (product rule)
- Number of ways to pick 3 reviewers from a team of 10: C(10,3) = 120 — order doesn't matter, so divide out the 3! orderings
Resources
Mastery checklist
- I can decide whether a counting problem needs the sum rule, product rule, or both
- I can explain when order matters (permutation) versus not (combination) and compute each
- I can apply inclusion–exclusion to a two- or three-set overlap problem
- I can estimate the size of a system's state space and use it to judge test feasibility