complementary counting

Sometimes the thing you want to count is sprawling and full of cases, while its OPPOSITE is short and simple. Complementary counting is the habit of counting the opposite instead, then subtracting from the total. The slogan is: instead of counting what you want directly, count everything, count what you do NOT want, and take the difference.

Formally, if S is the full set of possibilities and A is the subset you care about, then |A| = |S| - |not A|, where 'not A' is the complement. The classic trigger phrase is 'at least one'. Counting arrangements with 'at least one' of something usually means juggling many overlapping cases (exactly one, exactly two, ...), but its complement is the single tidy case 'none'. For example, the number of 4-digit PINs containing at least one 7 is hard to enumerate directly, but the total is 10^4 = 10000 and the PINs with NO 7 are 9^4 = 6561, so the answer is 10000 - 6561 = 3439.

In probability this is the complement rule, P(A) = 1 - P(not A), and it is one of the most useful shortcuts there is — the birthday problem is solved this way (compute the chance that all birthdays differ, then subtract from 1). The method is exact, not an approximation, as long as you have the total and the complement counted correctly. Just be sure the complement really is 'everything except A' with no overlap and nothing left out.