📋 Prerequisites

• Counting Basics
• Complementary Counting

When sets overlap, you can't just add their sizes — you'd double-count the overlap. The principle of inclusion-exclusion (PIE) fixes this: add the singles, subtract the pairs, add back the triples, and so on. It's the generalization of complementary counting to multiple forbidden conditions.

📚 Key Concepts

Two Sets: The Basic Case

For two sets A and B:

\[ |A \cup B| = |A| + |B| - |A \cap B| \]

Add both sets, then subtract the overlap that was counted twice.

Example: 30 students take math, 25 take physics, 10 take both. Total taking at least one = 30 + 25 - 10 = 45.

Three Sets

For three sets A, B, C:

\[ |A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C| \]

Pattern: add single sets, subtract pairwise intersections, add back triple intersection.

The triple intersection was subtracted too many times, so we add it back once.

General Inclusion-Exclusion Principle

For n sets $A_1, A_2, ..., A_n$:

\[ \left| \bigcup_{i=1}^{n} A_i \right| = \sum |A_i| - \sum |A_i \cap A_j| + \sum |A_i \cap A_j \cap A_k| - ... + (-1)^{n+1} |A_1 \cap ... \cap A_n| \]

Alternating sum over all non-empty subsets. Odd-sized intersections added, even-sized subtracted.

Total of \(2^{n}\) - 1 terms.

Complement Form (Most Useful)

Most competition problems ask "how many have NONE of the bad properties?"

If U is the total and $A_i$ are the sets of items with property i:

\[ |U - \bigcup A_i| = |U| - \sum |A_i| + \sum |A_i \cap A_j| - \sum |A_i \cap A_j \cap A_k| + ... + (-1)^n |A_1 \cap ... \cap A_n| \]

Items with none of the properties = Total - at least one property.

This is the form you'll use 90% of the time. "None of the bad things" is the complement of "at least one bad thing."

Derangements (错位排列)

A derangement is a permutation where no element appears in its original position.

Number of derangements of n elements, denoted !n:

\[ !n = n! \left(1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + ... + (-1)^n \frac{1}{n!}\right) \]

Classic PIE application: let A_{i} = permutations where element i is fixed. Count permutations with none fixed.

Examples: !3 = 2, !4 = 9, !5 = 44

Counting Divisible Numbers

"How many numbers from 1 to 100 are divisible by 2 or 3 or 5?"

Classic PIE problem. Count multiples of each, subtract multiples of pairwise products, add back multiples of lcm of all three.

⌊100/2⌋ + ⌊100/3⌋ + ⌊100/5⌋ - ⌊100/6⌋ - ⌊100/10⌋ - ⌊100/15⌋ + ⌊100/30⌋

Surjective Functions (Onto Functions)

Number of onto functions from an n-element set to a k-element set:

\[ \sum_{i=0}^{k} (-1)^i \binom{k}{i} (k-i)^n \]

PIE: total functions \(k^{n},\) minus those missing at least one element, add back those missing two, etc.

When to Use PIE

• Problem involves "at least one" of multiple types/properties
• Problem involves "none of" multiple forbidden conditions
• Counting derangements, onto functions, numbers divisible by multiple factors
• Complementary counting with multiple "bad" categories

Symmetry in PIE

Often all single-set sizes are equal, all pairwise intersections equal, etc. Then PIE simplifies:

$ |\bigcup A_i| = \binom{n}{1}|A_1| - \binom{n}{2}|A_1 \cap A_2| + \binom{n}{3}|A_1 \cap A_2 \cap A_3| - ... $

Use binomial coefficients to count how many terms of each size there are. This saves a lot of computation.

✏️ Example Problems