iii. Inclusion-Exclusion and Derangements

Count a union by adding the parts, subtracting double-counted pairs, adding back triples, and so on; more usefully, count the objects satisfying none of a set of conditions by counting those satisfying each subset of them, since intersections are simple constraints:
$\left|{\bigcup }_{i=1}^n{A}_i\right|={\sum }_{\varnothing \ne S\subseteq [n]}(-1{)}^{|S|+1}|{\bigcap }_{i\in S}{A}_i|,|\overline{A_1}\cap \cdots \cap \overline{A_n}|={\sum }_{S\subseteq [n]}(-1{)}^{|S|}\left|{\bigcap }_{i\in S}{A}_i\right|.$
It is the bridge to Möbius inversion, SOS DP and the derangement family. Bonferroni inequalities: truncating the alternating sum after an odd number of terms overestimates the union, after an even number underestimates it.

Problem	Sets $A_i$	Result
integers in $[1,n]$ coprime to $m$	divisible by the $i$-th prime factor of $m$	Euler’s totient for $n=m$
integers in $[1,n]$ divisible by none of $d_1..d_k$	divisible by $d_i$; intersections use lcm
derangements	”$i$ is a fixed point”	$D_n={\sum }_k(-1{)}^k(\genfrac{}{}{0ex}{}{n}{k})(n-k)!$
surjections $[n]\to [k]$	“box $i$ is empty”	${\sum }_j(-1{)}^j(\genfrac{}{}{0ex}{}{k}{j})(k-j{)}^n=k!S(n,k)$
colourings using all colours	same as surjections
permutations avoiding forbidden positions	rook numbers $r_k$ of the board	${\sum }_k(-1{)}^k{r}_k(n-k)!$
lattice paths avoiding cells	paths through each chosen cell	DP over cells sorted by position
$k$-tuples with $\gcd =1$ in $[1,n{]}^k$	Möbius form	${\sum }_d\mu (d)\lfloor n/d{\rfloor }^k$
distinct values in a range	Möbius-weighted counting

When $2^n$ terms are too many	Technique
sets indexed by divisors	Möbius function: $O(n)$ instead of $O(2^k)$ (Arithmetic Functions)
$|{\bigcap }_S{A}_i|$ depends only on $|S|$	collapse to ${\sum }_j(-1{)}^j(\genfrac{}{}{0ex}{}{n}{j})c_j$ (derangements, surjections): the most common escape
sets form a lattice or poset	Möbius function of the poset (below)
a value for every mask	SOS / subset-sum DP, $O(2^{n}n)$: SOS DP
only a few sets overlap	handle connected components of the overlap graph separately

ll countDivisibleByNone(ll n, const vector<ll>& d) {       // #x in [1, n] divisible by no d_i, O(2^k k)
    int k = sz(d); ll total = 0;
    for (int mask = 0; mask < (1 << k); mask++) {
        ll l = 1; bool big = false;
        for (int i = 0; i < k && !big; i++) if (mask >> i & 1) {
            ll g = gcd(l, d[i]);
            if (l / g > n / d[i]) big = true; else l = l / g * d[i];   // lcm > n contributes 0
        }
        if (!big) total += (__builtin_popcount(mask) % 2 ? -1 : 1) * (n / l);
    }
    return total;
}
 
mint surjections(ll n, int k, const Comb& cb) {           // functions [n] -> [k] hitting every box
    mint res = 0;
    for (int j = 0; j <= k; j++) { mint t = cb.C(k, j) * mint(k - j).pow(n); res += j % 2 ? -t : t; }
    return res;
}
 
vector<int> mobiusSieve(int n) {                           // mu[1..n], linear sieve
    vector<int> mu(n + 1, 0), primes; vector<char> comp(n + 1, 0); mu[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!comp[i]) primes.push_back(i), mu[i] = -1;
        for (int p : primes) { if ((ll)i * p > n) break; comp[i * p] = 1; if (i % p == 0) { mu[i * p] = 0; break; } mu[i * p] = -mu[i]; }
    }
    return mu;
}
 
ll coprimeTuples(int n, int k, const vector<int>& mu) {    // #(x_1..x_k) in [1, n]^k with gcd 1 (fits ll for small k)
    ll res = 0;
    for (int d = 1; d <= n; d++) if (mu[d]) { ll t = 1; for (int i = 0; i < k; i++) t *= n / d; res += mu[d] * t; }
    return res;
}

Proof: why the signs work, and Bonferroni

Fix an element lying in exactly $k$ of the sets. In the complement formula it is counted once for every subset $S$ of those $k$ sets, with sign $(-1{)}^{|S|}$: ${\sum }_{j=0}^k\left(\genfrac{}{}{0ex}{}{k}{j}\right)(-1{)}^j=(1-1{)}^k=[k=0]$. So elements in no set count 1 and all others 0. Bonferroni: truncating after the terms with $|S|\le t$ gives an element in exactly $k\ge 1$ sets the weight ${\sum }_{j=0}^t(-1{)}^j(\genfrac{}{}{0ex}{}{k}{j})=(-1{)}^t\left(\genfrac{}{}{0ex}{}{k-1}{t}\right)$ (alternating partial sum), whose sign is $(-1{)}^t$; so the truncated complement count is too large for even $t$ and too small for odd $t$, and the union bounds alternate correspondingly. Divisibility: $x$ is divisible by all $d_i$, $i\in S$, iff ${\mathrm{lcm}}_S{d}_i\mid x$, and there are $\lfloor n/\mathrm{lcm}\rfloor$ such $x$; an lcm above $n$ contributes 0, which also avoids overflow. Any $n\le 10^{18}$ has at most 15 distinct prime factors ($2\cdot 3\cdots 47>10^{18}$), so prime-factor enumerations are small. Möbius form: ${\sum }_{d\mid g}\mu (d)=[g=1]$, so ${\sum }_x[\gcd =1]={\sum }_d\mu (d)\#\{x:d\mid \text{all }{x}_i\}={\sum }_d\mu (d)\lfloor n/d{\rfloor }^k$; this is inclusion–exclusion over the prime divisors, with $\mu (d)$ the sign of the squarefree set of primes. Surjections: $|{\bigcap }_{i\in S}{A}_i|=(k-|S|{)}^n$. Checked against brute force.

Derangements

Permutations with no fixed point: $D_n$ = 1, 0, 1, 2, 9, 44, 265, 1854, 14833, 133496, …

Fact	Formula
inclusion–exclusion	$D_n={\sum }_{k=0}^n(-1{)}^k(\genfrac{}{}{0ex}{}{n}{k})(n-k)!=n!{\sum }_{k=0}^n\frac{(-1{)}^k}{k!}$
recurrences	$D_n=(n-1)(D_{n-1}+D_{n-2})$, $D_n=n{D}_{n-1}+(-1{)}^n$
nearest integer	$D_n=\lfloor \frac{n!}{e}+\frac{1}{2}\rfloor$ ($n\ge 1$): a random permutation is a derangement with probability $\to \frac{1}{e}\approx 0.3679$ (already 3 decimals at $n=6$: the hat-check problem)
exactly $k$ fixed points	$\left(\genfrac{}{}{0ex}{}{n}{k}\right)D_{n-k}$; summing over $k$: $n!={\sum }_k\left(\genfrac{}{}{0ex}{}{n}{k}\right)D_{n-k}$
expected fixed points	exactly 1 for every $n$ (linearity: each element is fixed with probability $\frac{1}{n}$)
EGF	$\frac{e^{-x}}{1-x}$ (Generating Functions)

Related count	Answer
permutations with all cycles of length $\ge 2$	derangements
involutions (${\sigma }^2=\mathrm{id}$)	$I_n=I_{n-1}+(n-1)I_{n-2}$: 1, 1, 2, 4, 10, 26, 76
permutations with exactly $k$ cycles	Stirling numbers of the first kind (Stirling and Bell)
no $i\mapsto i$ and no $i\mapsto i+1$ ($i<n$)	${\sum }_k(-1{)}^k(\genfrac{}{}{0ex}{}{2n-k}{k})(n-k)!$
ménage problem (seat $n$ couples around a table alternating men and women, nobody next to their partner; men’s seats fixed)	Touchard: $M_n={\sum }_{k=0}^n(-1{)}^k\frac{2n}{2n-k}(\genfrac{}{}{0ex}{}{2n-k}{k})(n-k)!$: 1, 0, 0, 1, 2, 13, 80, 579 for $n=\mathrm{0..7}$ (times $2\cdot n!$ for the full seating)
a random permutation has a cycle longer than $n/2$	probability ${\sum }_{k>n/2}\frac{1}{k}\to \ln 2\approx 0.693$: the 100 prisoners analysis

Forbidden positions in general. Permutations avoiding an arbitrary set of forbidden cells are counted by the permanent of the 0/1 allowed matrix (#P-hard in general; equivalently counting perfect matchings of a bipartite graph). Small $n$: Ryser’s formula in $O(2^{n}n)$. Structured boards: rook polynomials, $\#\{\text{avoiding }B\}={\sum }_k(-1{)}^k{r}_k(B)(n-k)!$ where $r_k$ counts placements of $k$ non-attacking rooks on $B$ (for the diagonal, $r_k=\left(\genfrac{}{}{0ex}{}{n}{k}\right)$: derangements; for the two diagonals $i\to i,i+1$: $r_k=\left(\genfrac{}{}{0ex}{}{2n-k}{k}\right)$; staircase boards: ménage-like formulas).

mint derangement(int n) { if (n == 0) return 1; mint a = 1, b = 0; for (int i = 2; i <= n; i++) { mint c = mint(i - 1) * (a + b); a = b; b = c; } return n == 1 ? 0 : b; }
 
mint menage(int n, const Comb& cb) {                       // Touchard, n >= 2 (men fixed); M_0 = 1, M_1 = 0
    if (n == 0) return 1;
    if (n == 1) return 0;
    mint res = 0;
    for (int k = 0; k <= n; k++) { mint t = mint(2 * n) / mint(2 * n - k) * cb.C(2 * n - k, k) * cb.f[n - k]; res += k % 2 ? -t : t; }
    return res;
}
 
ll permanentRyser(const vector<vector<ll>>& a) {           // per(A) = (-1)^n sum_S (-1)^|S| prod_i sum_{j in S} a_ij, O(2^n n) with Gray code
    int n = sz(a); if (n == 0) return 1;
    vector<ll> rowSum(n, 0); ll total = 0; int prev = 0;
    for (int g = 1; g < (1 << n); g++) {
        int cur = g ^ (g >> 1), diff = cur ^ prev, j = __builtin_ctz(diff); bool add = cur & diff;
        for (int i = 0; i < n; i++) rowSum[i] += add ? a[i][j] : -a[i][j];
        ll prod = 1; for (int i = 0; i < n; i++) prod *= rowSum[i];
        total += (__builtin_popcount(cur) % 2 ? -1 : 1) * prod;
        prev = cur;
    }
    return n % 2 ? -total : total;
}

Proof: the derangement formulas, ménage and Ryser

Inclusion–exclusion: with $A_i$ = ”$i$ fixed”, $|{\bigcap }_S{A}_i|=(n-|S|)!$. First recurrence: element 1 goes to some $j\ne 1$ ($n-1$ choices); if $j$ goes to 1, the other $n-2$ elements form a derangement ($D_{n-2}$); otherwise rename “position 1” as $j$‘s forbidden spot and the $n-1$ elements other than 1 form a derangement ($D_{n-1}$). Second recurrence: from the explicit sum, $D_n-n{D}_{n-1}=n!\frac{(-1{)}^n}{n!}$. Nearest integer: $|D_n-\frac{n!}{e}|=n!\left|{\sum }_{k>n}\frac{(-1{)}^k}{k!}\right|<\frac{1}{n+1}\le \frac{1}{2}$. Exactly $k$ fixed points: choose them and derange the rest. Long cycle: a permutation has at most one cycle longer than $\frac{n}{2}$, and the number with a cycle of length exactly $k>\frac{n}{2}$ is $\left(\genfrac{}{}{0ex}{}{n}{k}\right)(k-1)!(n-k)!=\frac{n!}{k}$, so the probability is ${\sum }_{k>n/2}\frac{1}{k}\to \ln 2$.

Rook polynomials: let $A_c$ = “the permutation uses forbidden cell $c$”; a set of cells can all be used only if they are non-attacking, and then $(n-k)!$ completions remain; grouping by $k$ gives ${\sum }_k(-1{)}^k{r}_k(n-k)!$. For “no $i\mapsto i$ or $i+1$” the forbidden cells form a path of $2n-1$ cells in which consecutive cells attack, and $k$ pairwise non-consecutive cells among $2n-1$ can be chosen in $\left(\genfrac{}{}{0ex}{}{2n-k}{k}\right)$ ways. Ménage: with the men seated, the women’s forbidden cells form a cycle of $2n$ cells (each woman cannot sit on either side of her husband), and $k$ non-adjacent cells on a $2n$-cycle can be chosen in $\frac{2n}{2n-k}\left(\genfrac{}{}{0ex}{}{2n-k}{k}\right)$ ways, which gives Touchard’s formula.

Ryser: expand ${\prod }_i{\sum }_{j\in S}{a}_{ij}$ as a sum over functions $\sigma :[n]\to S$; by inclusion–exclusion over the columns that $\sigma$ misses, ${\sum }_S(-1{)}^{n-|S|}{\prod }_i{\sum }_{j\in S}{a}_{ij}$ keeps exactly the surjective, i.e. bijective, $\sigma$, whose total is the permanent. The Gray code changes one column per step, so each row sum updates in $O(1)$. All functions were checked against brute force over permutations for $n\le 8$.

Möbius inversion on posets

For a locally finite poset, $\mu (x,x)=1$ and $\mu (x,y)=-{\sum }_{x\le z<y}\mu (x,z)$ for $x<y$ (0 if $x\nleqq y$). Then
$f(y)={\sum }_{x\le y}g(x)⟺g(y)={\sum }_{x\le y}\mu (x,y)f(x).$
Special cases: a chain gives differences ($g(n)=f(n)-f(n-1)$); the subset lattice gives $\mu (S,T)=(-1{)}^{|T\setminus S|}$, i.e. inclusion–exclusion and the SOS Möbius transform; the divisor lattice gives the number-theoretic $\mu (n/m)$; the partition lattice gives $\mu (\hat{0},\hat{1})=(-1{)}^{k-1}(k-1)!$ for $k$ blocks; a product of posets has the product Möbius function. In the incidence algebra (functions on pairs $x\le y$ with $(\alpha \beta )(x,y)={\sum }_{x\le z\le y}\alpha (x,z)\beta (z,y)$), $\mu$ is the inverse of the zeta function $\zeta \equiv 1$.

vector<vector<ll>> posetMobius(const vector<vector<char>>& le) {   // le[x][y]: x <= y; elements in a linear extension order
    int n = sz(le); vector<vector<ll>> mu(n, vector<ll>(n, 0));
    for (int x = 0; x < n; x++) {
        mu[x][x] = 1;
        for (int y = x + 1; y < n; y++) if (le[x][y]) {
            ll s = 0; for (int z = x; z < y; z++) if (le[x][z] && le[z][y]) s += mu[x][z];
            mu[x][y] = -s;
        }
    }
    return mu;
}

Proof: Möbius inversion on a poset

By definition ${\sum }_{x\le z\le y}\mu (x,z)=[x=y]$, i.e. $\mu \zeta =\delta$ in the incidence algebra; for finite posets a one-sided inverse is two-sided (triangular matrices in a linear extension), so also $\zeta \mu =\delta$: ${\sum }_{x\le z\le y}\mu (z,y)=[x=y]$. If $f(y)={\sum }_{x\le y}g(x)$ then ${\sum }_{x\le y}\mu (x,y)f(x)={\sum }_{x\le y}\mu (x,y){\sum }_{w\le x}g(w)={\sum }_{w\le y}g(w){\sum }_{w\le x\le y}\mu (x,y)=g(y)$; the converse is the same computation with $\zeta$. Subset lattice: the interval $[S,T]$ is a Boolean lattice of rank $r=|T\setminus S|$ and ${\sum }_j\left(\genfrac{}{}{0ex}{}{r}{j}\right)(-1{)}^j=[r=0]$ verifies the formula. Products: ${\mu }_{P\times Q}((x,x^{\prime }),(y,y^{\prime }))={\mu }_P(x,y){\mu }_Q(x^{\prime },y^{\prime })$ satisfies the defining recursion because sums over a product interval factor. The divisor lattice of $n=\prod p_i^{e_i}$ is a product of chains, giving the classical $\mu$. Checked on divisor and subset lattices.

Related notes

• Arithmetic Functions (Möbius)
• Submasks and SOS DP
• Bipartite Matching (permanents count perfect matchings)