Combinatorics

Combinatorics is the mathematics of counting without listing. Listing every outcome works for tiny problems, but once there are hundreds or millions of possibilities we need principles that let us count in a structured way. Three principles underpin the whole topic: the multiplication principle, the addition principle and the inclusion–exclusion principle.

Multiplication principle. If a task is completed in stages, where the first stage can be done in m ways and, for each of those, the second stage can be done in n ways, then the whole task can be done in m × n ways. This extends to any number of stages. The key word is and: you choose an entrée and a main and a dessert.

A tree diagram shows why the principle works: each branch at one stage splits into the same number of branches at the next stage.

Addition principle. If a task can be done in one of several mutually exclusive ways (they cannot happen together), the total number of ways is the sum of the numbers for each way. The key word is or: you travel by bus or by train. The cases must not overlap; if they do, simple addition double counts.

Inclusion–exclusion principle. When sets overlap, we correct for double counting. For two sets, |A ∪ B| = |A| + |B| − |A ∩ B|. Elements in both sets were counted twice, so we subtract them once. For three sets, |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|.

After subtracting the pairwise overlaps, the elements in all three sets have been added three times and subtracted three times, so they must be added back once. A Venn diagram is the best way to check this reasoning, and the number of elements in none of the sets is the total minus the union.

When reading a problem, ask: is this a sequence of stages (multiply), a choice between separate cases (add), or a count of overlapping categories (inclusion–exclusion)? Many exam questions combine all three, so state which principle you are using at each step.