Inclusion-Exclusion Principle: Counting With Overlaps the Right Way

Algorithm/Topic Statement#

The inclusion-exclusion principle is the master rule for counting elements that belong to the union of overlapping sets. The size of the union of two sets equals the sum of their sizes minus the size of their intersection. The size of the union of three sets adds back in the triple intersection that the pairwise subtractions removed twice. The full formula alternates: include single sets, exclude pairs, include triples, exclude quadruples, and so on. In algorithmic form you iterate over every nonempty subset of the input sets, compute the size of their joint intersection, and add or subtract based on the parity of the subset. This is the single most-used counting tool in competitive programming and the gateway to derangements, Euler totient, surjection counting, and divisibility problems.

Why This Topic Matters#

Counting problems with constraints almost always reduce to inclusion-exclusion. How many integers in 1 to n are divisible by 2 or 3 or 5? Inclusion-exclusion. How many permutations leave no element fixed? Inclusion-exclusion gives the derangement formula. How many ways to color a graph so that no two adjacent vertices share a color? Inclusion-exclusion underlies the chromatic polynomial. Even Euler totient, the count of integers up to n that are coprime to n, is a textbook inclusion-exclusion application. Interviewers at Google, Amazon, and Microsoft draw on this technique through problems like Ugly Number III, Sum of Multiples, and Nth Magical Number on LeetCode. Codeforces problems regularly demand inclusion-exclusion fused with bitmask iteration. The technique generalizes to set theory, probability, and even quantum computing through the Möbius inversion lens.

The Core Insight (math intuition + proof sketch)#

The intuition is bookkeeping. When you add the sizes of two overlapping sets you have counted their intersection twice, so you subtract it once. With three sets the triple intersection has been counted three times in the singletons, subtracted three times in the pairs, leaving a net count of zero. To restore it you add it back once. The alternating signs continue forever. The formal statement of inclusion-exclusion is that the size of the union of n sets equals the alternating sum, over every nonempty subset of those sets, of the size of the joint intersection of the subset, with sign equal to negative one to the size of the subset plus one.

The proof is a one-line bijection. Pick any element x in the union. Suppose x lies in exactly d of the sets. The element contributes to every subset whose chosen sets all contain x. There are exactly C of d choose k such subsets of size k. The total contribution of x to the alternating sum is the sum over k from one to d of negative one to the k plus one times C of d choose k. By the binomial theorem this equals one minus the quantity one minus one to the d, which simplifies to one. So every element contributes exactly one to the alternating sum, recovering the size of the union.

For applications to divisibility counting, the sets are A i meaning integers in 1 to n divisible by m i. The intersection of any subset of these sets is the set of integers divisible by the lcm of the chosen moduli, which has size n divided by the lcm. Plug into inclusion-exclusion to get the count of integers divisible by at least one of the moduli.

Visual Dry Run / Worked Example#

Count integers in 1 to 30 divisible by 2 or 3 or 5. Single sets contribute 30 divided by 2 plus 30 divided by 3 plus 30 divided by 5, which equals 15 plus 10 plus 6, totaling 31. Pairwise intersections are integers divisible by lcm of pairs. lcm of 2 and 3 is 6, contributing 30 divided by 6 equals 5. lcm of 2 and 5 is 10, contributing 3. lcm of 3 and 5 is 15, contributing 2. Subtract these to get 31 minus 5 minus 3 minus 2 equals 21. Triple intersection is divisible by lcm of 2, 3, 5 which is 30, contributing 1. Add this back to get 22. Verify by listing: 2, 3, 4, 5, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28, 30. That is 22 integers. Confirmed.

For derangements with n equal to 4, the formula D of n equals n factorial times the alternating sum over k from zero to n of negative one to the k divided by k factorial. For n equal to 4, this gives 24 times the quantity 1 minus 1 plus one half minus one sixth plus one twenty-fourth, which equals 24 times nine over twenty-four, equals 9. Verify by enumerating permutations of 1, 2, 3, 4 with no fixed point and counting; you will find exactly 9.

Solution / Implementation#

Python (bitmask inclusion-exclusion for divisibility, derangements)#

from math import gcd
 
def count_divisible_union(n, moduli):
    k = len(moduli)
    total = 0
    for mask in range(1, 1 << k):
        l = 1
        for i in range(k):
            if mask & (1 << i):
                l = l * moduli[i] // gcd(l, moduli[i])
                if l > n:
                    break
        bits = bin(mask).count('1')
        if bits % 2 == 1:
            total += n // l
        else:
            total -= n // l
    return total
 
def derangements(n, mod=10**9 + 7):
    if n == 0:
        return 1
    if n == 1:
        return 0
    dp = [0] * (n + 1)
    dp[0], dp[1] = 1, 0
    for i in range(2, n + 1):
        dp[i] = (i - 1) * (dp[i-1] + dp[i-2]) % mod
    return dp[n]
 
def euler_phi(n):
    result = n
    p = 2
    temp = n
    while p * p <= temp:
        if temp % p == 0:
            while temp % p == 0:
                temp //= p
            result -= result // p
        p += 1
    if temp > 1:
        result -= result // temp
    return result

JavaScript#

function gcd(a, b) {
  return b === 0n ? a : gcd(b, a % b);
}
 
function countDivisibleUnion(n, moduli) {
  const big = BigInt(n);
  const k = moduli.length;
  let total = 0n;
  for (let mask = 1; mask < (1 << k); mask++) {
    let l = 1n;
    let bits = 0;
    for (let i = 0; i < k; i++) {
      if (mask & (1 << i)) {
        const m = BigInt(moduli[i]);
        l = (l * m) / gcd(l, m);
        bits++;
        if (l > big) break;
      }
    }
    const term = big / l;
    if (bits % 2 === 1) total += term;
    else total -= term;
  }
  return Number(total);
}

Time complexity is order two to the k times k for the bitmask iteration with k moduli. For derangements the DP is order n. Euler totient by trial division is order square root of n.

Common Mistakes#

The most frequent mistake is forgetting to alternate signs based on subset size. Always tie the sign to the popcount of the bitmask, not to a manual toggle. Another classic error is computing the lcm in fixed-width integers when it can overflow. Use BigInt or 128-bit, or terminate the inner loop early when the running lcm already exceeds n. People also confuse inclusion-exclusion for the union with the formula for the complement. If you want the count of elements in none of the sets, use n minus the inclusion-exclusion sum. Watch for double counting when sets overlap heavily, like when the moduli share many common factors. Finally, do not use the principle blindly when you have many sets, because two to the k blows up; in those cases consider Möbius inversion or generating functions.

Interview Tips#

When you see at least one of, or none of, or exactly k of as the question structure, reach for inclusion-exclusion. Verbalize the sign alternation rule before writing code. If the number of conditions is small, like under twenty, use a bitmask iteration. If it is larger, consider Möbius inversion or a tailored counting approach. Mention concrete applications you know, like Euler totient and derangements, to demonstrate breadth. Always validate on a tiny example by hand before claiming the formula is correct.

Follow-up Questions#

How would you compute the number of surjections from an n-element set to a k-element set using inclusion-exclusion? Could you derive the chromatic polynomial of a small graph using inclusion-exclusion over edge constraints? What is Möbius inversion, and how does it generalize the alternating signs of inclusion-exclusion? Can you implement Bonferroni inequalities to bound the union size when computing all terms is too expensive?

Key Takeaways#

• Inclusion-exclusion alternates between adding and subtracting set intersections to count the union exactly.
• Iterate over every nonempty subset of the input sets via a bitmask, compute the joint intersection, and add or subtract by the popcount parity.
• Applications include divisibility counting, derangements, Euler totient, surjection counting, and chromatic polynomials.
• Watch for overflow in lcm computations and for the explosion of subsets when k is large.
• The technique generalizes to Möbius inversion in number theory and probability theory through the union bound family.
• Mastering inclusion-exclusion unlocks an enormous library of competitive programming and combinatorial interview problems.