Counting & ProbabilityDifficulty 25-90796 tagged problems

Inclusion-Exclusion

Inclusion-Exclusion is the habit of correcting overlapping counts by alternately adding and subtracting intersections. In contest math, that habit turns a crowded setup into a relation the student can test, bound, count, or compute. MathGrit teaches it as a recognizable signal, a deliberate move, and a final translation back to the original question.

Practice this technique Match my level

The Key Result

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

To count a union without double-counting, add the sizes of the sets, then subtract the overlaps (and add back triple overlaps, and so on).

Why It Works

1
Adding $|A| + |B|$ counts every element of $A \cap B$ twice — once in each set.
2
Subtracting $|A \cap B|$ removes that one extra count, so each element of the union is counted exactly once.
3
For three sets the same logic gives $|A \cup B \cup C| = |A| + |B| + |C| - |A\cap B| - |A\cap C| - |B\cap C| + |A\cap B\cap C|$.
4
In general you alternate signs by the number of sets in each intersection: add odd-sized intersections, subtract even-sized ones.

Worked Examples

Example 1

How many integers from $1$ to $100$ are divisible by $2$ or $3$?

1
Let $A$ = multiples of $2$ and $B$ = multiples of $3$.
2
$|A| = \lfloor 100/2 \rfloor = 50$ and $|B| = \lfloor 100/3 \rfloor = 33$.
3
The overlap is multiples of $\operatorname{lcm}(2,3) = 6$: $|A \cap B| = \lfloor 100/6 \rfloor = 16$.
4
Apply the formula: $50 + 33 - 16 = 67$.

Answer:

$67$

Warm-up

In a class of $30$ students, $18$ take French and $15$ take Spanish; $7$ take both. How many take neither?

1
Students taking at least one language: $|F \cup S| = |F| + |S| - |F \cap S| = 18 + 15 - 7 = 26$.
2
Everyone else takes neither: $30 - 26 = 4$.

Answer:

$4$

Contest level

How many integers from $1$ to $100$ are divisible by none of $2$, $3$, or $5$?

1
Count those divisible by at least one, then complement. Singles: $\lfloor 100/2 \rfloor = 50$, $\lfloor 100/3 \rfloor = 33$, $\lfloor 100/5 \rfloor = 20$.
2
Pairwise: $\lfloor 100/6 \rfloor = 16$, $\lfloor 100/10 \rfloor = 10$, $\lfloor 100/15 \rfloor = 6$. Triple: $\lfloor 100/30 \rfloor = 3$.
3
Inclusion-exclusion: $|A \cup B \cup C| = (50 + 33 + 20) - (16 + 10 + 6) + 3 = 103 - 32 + 3 = 74$.
4
Divisible by none: $100 - 74 = 26$.

Answer:

$26$

Olympiad / Challenge

How many ways can $4$ distinct gifts be given to $3$ distinct children so that every child receives at least one gift? (Surjections from a $4$-set onto a $3$-set.)

1
Total unrestricted assignments: each of the $4$ gifts goes to any of $3$ children, $3^4 = 81$.
2
Let $A_i$ be the assignments where child $i$ gets nothing. Subtract $|A_1 \cup A_2 \cup A_3|$.
3
$\sum|A_i| = 3 \cdot 2^4 = 48$ (each gift avoids one child); $\sum|A_i \cap A_j| = \binom{3}{2} \cdot 1^4 = 3$ (all gifts to the one remaining child); $|A_1 \cap A_2 \cap A_3| = 0$.
4
By inclusion-exclusion the number missing someone is $48 - 3 + 0 = 45$, so surjections $= 81 - 45 = 36$. (Equivalently $3! \cdot S(4,3) = 6 \cdot 6 = 36$.)

Answer:

$36$

Going Deeper

The general statement is $|A_1 \cup \cdots \cup A_n| = \sum |A_i| - \sum |A_i \cap A_j| + \cdots + (-1)^{n-1}|A_1 \cap \cdots \cap A_n|$: alternate signs by the number of sets in each intersection. It is the engine behind derangements, Euler's totient $\varphi(n) = n\prod_{p \mid n}(1 - 1/p)$, and counting surjections.
It appears whenever you must count objects avoiding several forbidden properties at once ('divisible by none,' 'every box nonempty,' 'no fixed points'). When the sets are symmetric, the formula collapses to $\sum_k (-1)^k \binom{n}{k} \cdot (\text{size of a } k\text{-fold intersection})$, which is far quicker than naming each set.
Pitfall: get the signs and the intersection sizes right. The single most common slip is forgetting to add back the triple overlap (the $+|A \cap B \cap C|$ term), which leaves the inner region counted $0$ times instead of once. Always sanity-check a small intersection by hand, and remember the formula counts the union — the 'avoids everything' count is the universe minus that union.

Spot the Signal

Look for problems where the key step is correcting overlapping counts by alternately adding and subtracting intersections.
You can describe the hard part as correcting overlapping counts by alternately adding and subtracting intersections, but a direct attack starts producing clutter.
The problem rewards preserving structure instead of expanding, listing, or guessing too early.

Learn the Move

Start by identify the counting object that calls for inclusion-exclusion, then rewrite the givens around it.
Name the relation that makes Inclusion-Exclusion legal before doing computation.
Use the new relation to replace the messiest part of the problem with a cleaner one.
Translate the result back to the quantity the problem actually asks for.

Avoid These Traps

Do not use Inclusion-Exclusion just because the surface looks familiar; verify the required condition first.
Applying Inclusion-Exclusion because it sounds relevant, without checking the trigger first.
Stopping after spotting the technique instead of finishing the calculation or proof.

MathGrit Coach Note

Let inclusion-exclusion reveal the counting structure; then compute only what remains.

Try it on:

Practice a contest problem where the key step is correcting overlapping counts by alternately adding and subtracting intersections.

Back to techniques

Counting & ProbabilityDifficulty 25-90796 tagged problems

Inclusion-Exclusion

Practice this technique Match my level

The Key Result

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

To count a union without double-counting, add the sizes of the sets, then subtract the overlaps (and add back triple overlaps, and so on).

Why It Works

1
Adding $|A| + |B|$ counts every element of $A \cap B$ twice — once in each set.
2
Subtracting $|A \cap B|$ removes that one extra count, so each element of the union is counted exactly once.
3
For three sets the same logic gives $|A \cup B \cup C| = |A| + |B| + |C| - |A\cap B| - |A\cap C| - |B\cap C| + |A\cap B\cap C|$.
4
In general you alternate signs by the number of sets in each intersection: add odd-sized intersections, subtract even-sized ones.

Worked Examples

Example 1

How many integers from $1$ to $100$ are divisible by $2$ or $3$?

1
Let $A$ = multiples of $2$ and $B$ = multiples of $3$.
2
$|A| = \lfloor 100/2 \rfloor = 50$ and $|B| = \lfloor 100/3 \rfloor = 33$.
3
The overlap is multiples of $\operatorname{lcm}(2,3) = 6$: $|A \cap B| = \lfloor 100/6 \rfloor = 16$.
4
Apply the formula: $50 + 33 - 16 = 67$.

Answer:

$67$

Warm-up

In a class of $30$ students, $18$ take French and $15$ take Spanish; $7$ take both. How many take neither?

1
Students taking at least one language: $|F \cup S| = |F| + |S| - |F \cap S| = 18 + 15 - 7 = 26$.
2
Everyone else takes neither: $30 - 26 = 4$.

Answer:

$4$

Contest level

How many integers from $1$ to $100$ are divisible by none of $2$, $3$, or $5$?

1
Count those divisible by at least one, then complement. Singles: $\lfloor 100/2 \rfloor = 50$, $\lfloor 100/3 \rfloor = 33$, $\lfloor 100/5 \rfloor = 20$.
2
Pairwise: $\lfloor 100/6 \rfloor = 16$, $\lfloor 100/10 \rfloor = 10$, $\lfloor 100/15 \rfloor = 6$. Triple: $\lfloor 100/30 \rfloor = 3$.
3
Inclusion-exclusion: $|A \cup B \cup C| = (50 + 33 + 20) - (16 + 10 + 6) + 3 = 103 - 32 + 3 = 74$.
4
Divisible by none: $100 - 74 = 26$.

Answer:

$26$

Olympiad / Challenge

How many ways can $4$ distinct gifts be given to $3$ distinct children so that every child receives at least one gift? (Surjections from a $4$-set onto a $3$-set.)

1
Total unrestricted assignments: each of the $4$ gifts goes to any of $3$ children, $3^4 = 81$.
2
Let $A_i$ be the assignments where child $i$ gets nothing. Subtract $|A_1 \cup A_2 \cup A_3|$.
3
$\sum|A_i| = 3 \cdot 2^4 = 48$ (each gift avoids one child); $\sum|A_i \cap A_j| = \binom{3}{2} \cdot 1^4 = 3$ (all gifts to the one remaining child); $|A_1 \cap A_2 \cap A_3| = 0$.
4
By inclusion-exclusion the number missing someone is $48 - 3 + 0 = 45$, so surjections $= 81 - 45 = 36$. (Equivalently $3! \cdot S(4,3) = 6 \cdot 6 = 36$.)

Answer:

$36$

Going Deeper

The general statement is $|A_1 \cup \cdots \cup A_n| = \sum |A_i| - \sum |A_i \cap A_j| + \cdots + (-1)^{n-1}|A_1 \cap \cdots \cap A_n|$: alternate signs by the number of sets in each intersection. It is the engine behind derangements, Euler's totient $\varphi(n) = n\prod_{p \mid n}(1 - 1/p)$, and counting surjections.
It appears whenever you must count objects avoiding several forbidden properties at once ('divisible by none,' 'every box nonempty,' 'no fixed points'). When the sets are symmetric, the formula collapses to $\sum_k (-1)^k \binom{n}{k} \cdot (\text{size of a } k\text{-fold intersection})$, which is far quicker than naming each set.
Pitfall: get the signs and the intersection sizes right. The single most common slip is forgetting to add back the triple overlap (the $+|A \cap B \cap C|$ term), which leaves the inner region counted $0$ times instead of once. Always sanity-check a small intersection by hand, and remember the formula counts the union — the 'avoids everything' count is the universe minus that union.

Spot the Signal

Look for problems where the key step is correcting overlapping counts by alternately adding and subtracting intersections.
You can describe the hard part as correcting overlapping counts by alternately adding and subtracting intersections, but a direct attack starts producing clutter.
The problem rewards preserving structure instead of expanding, listing, or guessing too early.

Learn the Move

Start by identify the counting object that calls for inclusion-exclusion, then rewrite the givens around it.
Name the relation that makes Inclusion-Exclusion legal before doing computation.
Use the new relation to replace the messiest part of the problem with a cleaner one.
Translate the result back to the quantity the problem actually asks for.

Avoid These Traps

Do not use Inclusion-Exclusion just because the surface looks familiar; verify the required condition first.
Applying Inclusion-Exclusion because it sounds relevant, without checking the trigger first.
Stopping after spotting the technique instead of finishing the calculation or proof.

MathGrit Coach Note

Let inclusion-exclusion reveal the counting structure; then compute only what remains.

Try it on:

Practice a contest problem where the key step is correcting overlapping counts by alternately adding and subtracting intersections.