Inclusion–exclusion principle

General form

THEOREM

For finite sets $A_1,\dots ,A_n$,

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

Equivalently,

$$\left|\bigcup _{i=1}^n{A}_i\right|=\sum _i|A_i|-\sum _{i<j}|A_i\cap A_j|+\sum _{i<j<k}|A_i\cap A_j\cap A_k|-\cdots +(-1{)}^{n+1}|A_1\cap \cdots \cap A_n|.$$

For $n=2$ $|A_1\cup A_2|=|A_1|+|A_2|-|A_1\cap A_2|$

For $n=3$: $|A_1\cup A_2\cup A_3|=|A_1|+|A_2|+|A_3|-|A_1\cap A_2|-|A_2\cap A_3|-|A_1\cap A_3|+|A_1\cap A_2\cap A_3|$

Proof

Pick an element $x$ and suppose it lies in exactly $r$ of the sets $A_1,\dots ,A_n$.

Then on the right-hand side:

• $x$ is counted in exactly $\left(\genfrac{}{}{0ex}{}{r}{1}\right)$ single sets,
• subtracted in exactly $\left(\genfrac{}{}{0ex}{}{r}{2}\right)$ pairwise intersections,
• added in exactly $\left(\genfrac{}{}{0ex}{}{r}{3}\right)$ triple intersections,
• and so on.

So the total contribution of $x$ to the right-hand side is

$$\left(\genfrac{}{}{0ex}{}{r}{1}\right)-\left(\genfrac{}{}{0ex}{}{r}{2}\right)+\left(\genfrac{}{}{0ex}{}{r}{3}\right)-\cdots +(-1{)}^{r+1}(\genfrac{}{}{0ex}{}{r}{r}).$$

Using

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

we get

$$\left(\genfrac{}{}{0ex}{}{r}{1}\right)-\left(\genfrac{}{}{0ex}{}{r}{2}\right)+\left(\genfrac{}{}{0ex}{}{r}{3}\right)-\cdots +(-1{)}^{r+1}(\genfrac{}{}{0ex}{}{r}{r})=1.$$

So every element in the union is counted exactly once. An element outside the union has $r=0$, so it contributes $0$ on both sides. Therefore both sides count exactly the same elements with the same multiplicity, which proves the formula.

Enumerating the subsets in code

In programming problems, the sets in the inclusion-exclusion formula are usually traversed with a bitmask.

For n sets, every integer mask from 1 to (1 << n) - 1 represents one non-empty subset of $\{1,\dots ,n\}$:

• bit i is 1 if and only if the subset contains the i-th set
• Integer.bitCount(mask) gives the size of the subset
• odd subset size means add the intersection term
• even subset size means subtract the intersection term

For divisibility problems, if $A_i$ is the set of numbers divisible by a[i], then for a chosen subset the intersection size is often computed with the lcm:

$$\left|\bigcap _{i\in I}{A}_i\right|=\lfloor \frac{N}{\mathrm{lcm}(a_i:i\in I)}\rfloor .$$

Example:

public static void testCase() {
    int n = In.readInt();
    long[] a = new long[n];
    for (int i = 0; i < n; i++) {
        a[i] = In.readInt();
    }
 
    long N = (long) Math.pow(10, 10), res = N;
 
    for (int mask = 1; mask < (1 << n); mask++) {
        long lcm = 1;
        int bits = Integer.bitCount(mask);
 
        for (int i = 0; i < n; i++) {
            if ((mask & (1 << i)) != 0) {
                lcm = (lcm * a[i]) / gcd(lcm, a[i]);
            }
        }
 
        res = bits % 2 == 1 ? res - N / lcm : res + N / lcm;
    }
 
    Out.println(res);
}
 
public static long gcd(long a, long b) {
    return b == 0 ? a : gcd(b, a % b);
}

Here:

• the loop over mask enumerates all non-empty subsets
• bits is the subset size
• lcm represents the intersection of the chosen divisibility sets
• N / lcm is the number of integers in 1..N divisible by all chosen numbers
• since res starts as N, this code computes how many integers in 1..N are divisible by none of the numbers in a