Inclusion-Exclusion

Count a union by adding the parts, subtracting the double-counted pairs, adding back the triples, and so on.

$\left|{\bigcup }_{i=1}^n{A}_i\right|={\sum }_{\varnothing \ne S\subseteq [n]}(-1{)}^{|S|+1}\left|{\bigcap }_{i\in S}{A}_i\right|.$

Equivalently, for the complement — usually the more useful form:

$\left|\overline{A_1}\cap \cdots \cap \overline{A_n}\right|={\sum }_{S\subseteq [n]}(-1{)}^{|S|}\left|{\bigcap }_{i\in S}{A}_i\right|.$

Why the signs work

Fix an element belonging to exactly $k\ge 1$ of the sets. It is counted once for every subset $S$ of those $k$ sets, with sign $(-1{)}^{|S|}$, giving

${\sum }_{j=0}^k\left(\genfrac{}{}{0ex}{}{k}{j}\right)(-1{)}^j=(1-1{)}^k=0,$

so it contributes exactly $0$ to the complement count — as it should, since it is in at least one set. An element in none of the sets contributes only through $S=\varnothing$, i.e. $+1$. $■$

The whole method is that one binomial identity.

The direct implementation

long long countCoprimeUpTo(long long n, vector<long long> primes) {
    int k = primes.size();
    long long total = 0;
    for (int mask = 0; mask < (1 << k); mask++) {
        long long prod = 1;
        for (int i = 0; i < k; i++) if (mask >> i & 1) prod *= primes[i];
        int bits = __builtin_popcount(mask);
        total += (bits % 2 ? -1 : 1) * (n / prod);
    }
    return total;
}

$O(2^{k}k)$. Since $2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17\cdot 19\cdot 23>2\cdot 10^8$, any $n\le 10^{18}$ has at most 15 distinct prime factors, so the enumeration is small.

Standard applications

Problem	Setup
Count integers in $[1,n]$ coprime to $m$	$A_i$ = divisible by the $i$-th prime factor of $m$ — gives Euler’s totient
Count integers divisible by none of $d_1..d_k$	$A_i$ = divisible by $d_i$; intersections use $\mathrm{lcm}$
Derangements	$A_i$ = ”$i$ is a fixed point”
Surjections from $[n]$ to $[k]$	$A_i$ = ”$i$ is not hit”: ${\sum }_j(-1{)}^j(\genfrac{}{}{0ex}{}{k}{j})(k-j{)}^n$
Count permutations avoiding forbidden positions	rook polynomials
Paths avoiding a set of cells	subtract paths through each cell
Colourings with all colours used	surjection count
Distinct values in a range	Mobius-weighted counting
Count $k$-tuples with $\gcd =1$	${\sum }_d\mu (d)\lfloor n/d{\rfloor }^k$

The Möbius connection

Möbius inversion is inclusion-exclusion on the divisor lattice: $\mu (d)$ is exactly the $(-1{)}^{|S|}$ sign, and squarefree $d$ correspond to the subsets $S$. Whenever a problem is “count things coprime to / not divisible by”, the Möbius form

${\sum }_{d=1}^n\mu (d)f(d)$

is inclusion-exclusion written compactly, and it runs in $O(n)$ instead of $O(2^k)$.

long long coprimePairs(int n) {                   // pairs (a,b) in [1,n]^2 with gcd 1
    long long res = 0;
    for (int d = 1; d <= n; d++) res += (long long)mu[d] * (n / d) * (n / d);
    return res;
}

When $2^n$ is too large

The direct sum is exponential in the number of sets. Three ways out:

Situation	Technique
Sets indexed by divisors	Möbius — linear in $n$
The intersection size depends only on $|S|$	collapse to ${\sum }_j(-1{)}^j(\genfrac{}{}{0ex}{}{n}{j})c_j$
Sets form a lattice or poset	Möbius function of that poset
Subset sums needed for all masks	SOS DP, $O(2^{n}n)$
Only a few sets actually overlap	build a graph and handle components separately

The second row is the most common escape: in derangements and surjections, $|A_{i_1}\cap \cdots \cap A_{i_j}|$ depends only on $j$, which turns $2^n$ terms into $n+1$.

The Bonferroni inequalities

Truncating the alternating sum gives bounds, not just an exact value: stopping after an even number of terms underestimates the union, after an odd number overestimates it. Useful when the full sum is intractable but a bound suffices.

Why it is worth knowing

It converts “count things satisfying none of these conditions” — usually hard — into “count things satisfying each subset of conditions” — usually easy, because intersections are simple constraints. That reframing is the core of most counting problems in contests, and it is the bridge to Möbius inversion, SOS DP, and the derangement family.

See also: Combinatorics · Möbius Function · SOS DP · Derangements