Section 1.3

Complements and Inclusion-Exclusion

Counting the complement ('at least one', 'contains a 0') and inclusion-exclusion over overlapping conditions, including derangement counts.

Toolkit

When “at least one” or “some forbidden pattern” conditions make direct counting hard, count the complement or combine overlapping conditions via inclusion-exclusion.

|A^c| = |S| - |A|, \qquad \mathbb{P}(A) = 1-\mathbb{P}(A^c).

For two events,

|A\cup B| = |A|+|B|-|A\cap B|,

and more generally

\left|\bigcup_i A_i\right| = \sum_i |A_i| - \sum_{i<j}|A_i\cap A_j| + \sum_{i<j<k}|A_i\cap A_j\cap A_k| - \cdots

Typical strategy: identify the “bad” or “easy-to-count” structure (all digits distinct, no symbol repeated, derangement, forbidden pattern) whose count is tractable, then subtract from the total count of unrestricted objects. When multiple constraints overlap, enumerate each intersection size explicitly rather than guessing — overlaps are often small and can be listed by hand. For derangement-type counts, recall

D_n = n!\sum_{k=0}^n \frac{(-1)^k}{k!}.

Problems