7.5 Enumeration and casework

Counting formulas are useful when a problem has a regular pattern. A short problem with several different restrictions may be easier to solve by listing the possibilities systematically. This is exhaustive enumeration: examine every relevant case exactly once. The key is a plan for the list, so that a missing or repeated case does not silently change the answer.

This is foundational to intermediate discrete reasoning. OpenStax's tables and trees show ways to list multistage outcomes; MIT's casework notes show why the cases must cover all possibilities. Review the addition and multiplication rules if a table cell itself contains several choices.

A basic idea: let one choice organise the rest

Find nonnegative integer solutions of $x+y+z=6$ when $x\le2$, $y\le2$, and $z\le3$. Choose $x$ and $y$ first; then $z=6-x-y$ is forced. There are only nine $(x,y)$ pairs to inspect. Because $z\le3$, we need $x+y\ge3$. Only $(1,2)$, $(2,1)$, and $(2,2)$ pass. They give $z=3,3,2$, so there are three solutions.

A quick tour of systematic casework

Choose an organising variable with few values, such as $x=0,1,2$. Within each case, list the remaining choices in a fixed order. A table works well for two short ranges; a tree works when later choices depend on earlier ones. If the final choice is determined by previous ones, calculate it rather than branching over it again.

Check coverage: every valid outcome must appear somewhere. Check separation: no outcome may appear in two cases. These are the same conditions needed before adding case counts in Module 7.1. A small exhaustive list can also reveal a pattern, but a pattern noticed in a few cases is not by itself a proof for larger inputs.

Enumeration grows rapidly. Four binary choices give $2^4=16$ candidates; twenty give over a million. For large spaces, look for a formula, an invariant, or a more efficient algorithm. Here we stay with small finite cases that can be checked completely.

Application 1: bounded solutions

Count triples of nonnegative integers satisfying $x+y+z=6$, $x,y\le2$, and $z\le3$.

1. If $x=0$, even $y=2$ leaves $z=4$, so there is no solution.
2. If $x=1$, only $y=2$ gives $z\le3$: $(1,2,3)$.
3. If $x=2$, $y=1$ or $2$ works: $(2,1,3)$ and $(2,2,2)$. The cases cover $x=0,1,2$ without overlap, giving $3$ solutions.

Application 2: selecting compatible features

A small model may use exactly two features from $A,B,C,D$. If $A$ is selected, $B$ must also be selected; $C$ and $D$ cannot be selected together. How many two-feature sets are valid?

1. List the six unordered pairs once: $AB,AC,AD,BC,BD,CD$.
2. $AC$ and $AD$ fail the $A\Rightarrow B$ rule. $CD$ fails the incompatibility rule.
3. The valid sets are $AB,BC,BD$: three choices. Listing unordered pairs avoids counting $AB$ and $BA$ separately.