Inclusion-Exclusion Principle

July 2026 · 25 min read

The Principle

The Inclusion-Exclusion Principle (PIE) is one of the most versatile counting tools in combinatorics. At its heart, it answers a simple question: How many elements belong to at least one of several sets?

If you naïvely add up the sizes of the sets, you over-count elements that appear in multiple sets. PIE corrects for this by alternately subtracting and adding back the sizes of intersections.

For two sets, the formula is familiar:

|A ∪ B| = |A| + |B| − |A ∩ B|

This principle extends to any number of sets, and its applications in competitive programming are vast — from counting derangements to computing Euler's totient function.

Two and Three Set Cases

Two Sets

|A ∪ B| = |A| + |B| − |A ∩ B|

Example: In a class of 30 students, 18 take math and 15 take physics. If 10 take both, how many take at least one? 18 + 15 − 10 = 23.

Three Sets

|A ∪ B ∪ C| = |A| + |B| + |C|
            − |A∩B| − |A∩C| − |B∩C|
            + |A∩B∩C|

Example: Count integers from 1 to 100 divisible by 2, 3, or 5.

• |A| = ⌊100/2⌋ = 50 (divisible by 2)
• |B| = ⌊100/3⌋ = 33 (divisible by 3)
• |C| = ⌊100/5⌋ = 20 (divisible by 5)
• |A∩B| = ⌊100/6⌋ = 16
• |A∩C| = ⌊100/10⌋ = 10
• |B∩C| = ⌊100/15⌋ = 6
• |A∩B∩C| = ⌊100/30⌋ = 3

Answer = 50 + 33 + 20 − 16 − 10 − 6 + 3 = 74

General PIE Formula

For n sets A₁, A₂, …, Aₙ:

|A₁ ∪ A₂ ∪ … ∪ Aₙ| =   Σ|Aᵢ|  −  Σ|Aᵢ∩Aⱼ|  +  Σ|Aᵢ∩Aⱼ∩Aₖ|  −  …  + (−1)ⁿ⁺¹|A₁∩…∩Aₙ|

More compactly, summing over all non-empty subsets S ⊆ {1, …, n}:

|⋃ Aᵢ| = Σ_{∅≠S⊆[n]}  (−1)^(|S|+1)  ·  |⋂_{i∈S} Aᵢ|

Often we want the complement: count elements in none of the sets. If the universal set has size U:

|Ā₁ ∩ Ā₂ ∩ … ∩ Āₙ| = U − |A₁ ∪ … ∪ Aₙ|
                      = Σ_{S⊆[n]}  (−1)^|S|  ·  |⋂_{i∈S} Aᵢ|

Note: when S = ∅, the intersection is the entire universe, so the S = ∅ term contributes +U.

Counting Derangements

A derangement is a permutation where no element appears in its original position. Let D(n) denote the number of derangements of n elements.

Let Aᵢ = set of permutations that fix element i. We want permutations that avoid all Aᵢ:

D(n) = n! − |A₁ ∪ A₂ ∪ … ∪ Aₙ|

By PIE, |⋂_{i∈S} Aᵢ| = (n − |S|)! (fix the elements in S, permute the rest). There are C(n, |S|) subsets of size |S|:

D(n) = Σ_{k=0}^{n}  (−1)ᵏ · C(n, k) · (n − k)!
     = Σ_{k=0}^{n}  (−1)ᵏ · n! / k!
     = n! · Σ_{k=0}^{n}  (−1)ᵏ / k!

For large n, D(n) ≈ n!/e (rounded to the nearest integer).

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;
const int MAXN = 2e6 + 5;
long long fac[MAXN], inv_fac[MAXN];

long long power(long long a, long long b, long long mod) {
    long long res = 1; a %= mod;
    while (b > 0) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod; b >>= 1;
    }
    return res;
}

void precompute() {
    fac[0] = 1;
    for (int i = 1; i < MAXN; i++)
        fac[i] = fac[i - 1] * i % MOD;
    inv_fac[MAXN - 1] = power(fac[MAXN - 1], MOD - 2, MOD);
    for (int i = MAXN - 2; i >= 0; i--)
        inv_fac[i] = inv_fac[i + 1] * (i + 1) % MOD;
}

// Derangement D(n) mod p
long long derangement(int n) {
    long long ans = 0;
    for (int k = 0; k <= n; k++) {
        long long term = fac[n] % MOD * inv_fac[k] % MOD;
        if (k & 1) ans = (ans - term + MOD) % MOD;
        else        ans = (ans + term) % MOD;
    }
    return ans;
}

// O(n) derangement via recurrence
long long derangement_rec(int n) {
    if (n == 0) return 1;
    if (n == 1) return 0;
    long long dp0 = 1, dp1 = 0;
    for (int i = 2; i <= n; i++) {
        long long dp2 = (long long)(i - 1) % MOD * ((dp1 + dp0) % MOD) % MOD;
        dp0 = dp1;
        dp1 = dp2;
    }
    return dp1;
}

Counting Surjections

A surjection (onto function) from an n-set to an m-set hits every element in the codomain. Let S(n, m) denote the number of surjections.

Let Aⱼ = functions that miss element j in the codomain. Then |⋂_{j∈T} Aⱼ| = (m − |T|)ⁿ.

S(n, m) = mⁿ − |A₁ ∪ … ∪ Aₘ|
        = Σ_{k=0}^{m}  (−1)ᵏ · C(m, k) · (m − k)ⁿ

// Count surjections from n-set to m-set, mod prime
long long surjections(int n, int m) {
    long long ans = 0;
    for (int k = 0; k <= m; k++) {
        long long term = C(m, k) % MOD * power(m - k, n, MOD) % MOD;
        if (k & 1) ans = (ans - term + MOD) % MOD;
        else        ans = (ans + term) % MOD;
    }
    return ans;
}

Euler's Totient via PIE

Euler's totient function φ(n) counts integers from 1 to n that are coprime to n. Let the prime factorization of n be p₁^a₁ · p₂^a₂ · … · pₖ^aₖ.

Let Aᵢ = multiples of pᵢ in {1, …, n}. Then φ(n) = n − |A₁ ∪ … ∪ Aₖ|. Applying PIE:

φ(n) = n · Π_{p|n}  (1 − 1/p)

This classical formula is a direct consequence of inclusion-exclusion over the prime divisors of n.

// Euler's totient function
long long euler_totient(long long n) {
    long long result = n;
    for (long long p = 2; p * p <= n; p++) {
        if (n % p == 0) {
            while (n % p == 0) n /= p;
            result -= result / p;
        }
    }
    if (n > 1) result -= result / n;
    return result;
}

Sieve of Eratosthenes Connection

The Sieve of Eratosthenes can be viewed through the lens of inclusion-exclusion. To count primes up to N, we want numbers not divisible by any prime ≤ √N.

Let Aₚ = composites divisible by prime p. Primes up to N (plus 1 for the number 1 adjustment) are approximately:

π(N) ≈ N − |A₂ ∪ A₃ ∪ A₅ ∪ … |

The sieve eliminates composites one prime at a time — this is essentially the inclusion-exclusion process, but done greedily (sieving) rather than via the full formula.

// Sieve of Eratosthenes — the inclusion-exclusion engine
vector<int> sieve(int n) {
    vector<bool> is_prime(n + 1, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; (long long)i * i <= n; i++) {
        if (is_prime[i]) {
            for (int j = i * i; j <= n; j += i)
                is_prime[j] = false;
        }
    }
    vector<int> primes;
    for (int i = 2; i <= n; i++)
        if (is_prime[i]) primes.push_back(i);
    return primes;
}

Bitmask Implementation

The most common CP technique for PIE is bitmask enumeration. Given m "bad" properties, we iterate over all 2ᵐ subsets and apply the alternating sign based on subset size.

// Generic PIE template using bitmasks
// properties: array of m "property descriptors"
// count_intersection(mask): returns |intersection of properties in mask|
//   (for mask=0, returns the universal set size)

long long pie_bitmask(int m, function<long long(int)> count_intersection) {
    long long ans = 0;
    for (int mask = 0; mask < (1 << m); mask++) {
        int bits = __builtin_popcount(mask);
        long long val = count_intersection(mask);
        if (bits & 1) ans -= val;
        else           ans += val;
    }
    return ans;  // count of elements with NONE of the properties
}

Example: Count integers 1..N not divisible by any of the given primes

// Count integers in [1, N] coprime to all primes in p[]
long long count_coprime(long long N, vector<long long>& p) {
    int m = p.size();
    long long ans = 0;
    for (int mask = 0; mask < (1 << m); mask++) {
        long long prod = 1;
        int bits = 0;
        for (int i = 0; i < m; i++) {
            if (mask & (1 << i)) {
                prod *= p[i];
                bits++;
            }
        }
        long long cnt = N / prod;
        if (bits & 1) ans -= cnt;
        else           ans += cnt;
    }
    return ans;
}

Optimized PIE with Early Termination

If the intersection size drops to zero for large subsets, we can skip them:

long long pie_optimized(long long N, vector<long long>& divisors) {
    int m = divisors.size();
    long long ans = 0;
    for (int mask = 0; mask < (1 << m); mask++) {
        long long prod = 1;
        int bits = 0;
        bool overflow = false;
        for (int i = 0; i < m && !overflow; i++) {
            if (mask & (1 << i)) {
                bits++;
                if (prod > N / divisors[i]) { overflow = true; break; }
                prod *= divisors[i];
            }
        }
        if (overflow) continue;
        long long cnt = N / prod;
        if (bits & 1) ans -= cnt;
        else           ans += cnt;
    }
    return ans;
}

Practice Problems

Master PIE with these carefully chosen problems:

1. Coprime Count — Count integers in [1, N] coprime to a given number M. Factor M and apply PIE over its prime factors.
2. Derangements (CSES) — Compute D(n) for n ≤ 10⁶. Use the recurrence for O(n) or the PIE formula.
3. Surjections — Count onto functions from {1, …, n} to {1, …, m} modulo 10⁹ + 7.
4. At Least One Divisor — Given primes p₁, …, pₖ, count integers in [1, N] divisible by at least one.
5. Stars and Bars with Caps — Use PIE to handle upper bounds in distribution problems (connects back to the previous post).
6. Euler Totient Sieve — Compute φ(n) for all n ≤ 10⁷ using a sieve. Verify against the PIE formula for individual values.
7. Forbidden Positions (Problematic Queens variant) — Place n non-attacking rooks on an n×n board with some squares forbidden. Uses PIE over forbidden patterns.

Summary of PIE Applications