Inclusion–exclusion and derangements

MATH-260 proved the two-set rule \(|A \cup B| = |A| + |B| - |A \cap B|\). Counting the union of many overlapping sets needs the general principle of inclusion and exclusion. It is one of the most useful tools in enumeration, because it converts a count with a forbidden property (no fixed points, no empty boxes, no common factors) into an alternating sum of counts that are easy because they impose properties rather than forbid them.

The principle

Theorem (inclusion–exclusion). For finite sets \(A_1, \ldots, A_n\), \[\Big|\bigcup_{i=1}^n A_i\Big| = \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|.\] More compactly, writing \(A_S = \bigcap_{i \in S} A_i\) for a nonempty index set \(S\), \[\Big|\bigcup_i A_i\Big| = \sum_{\emptyset \ne S \subseteq [n]} (-1)^{|S|+1}|A_S|.\]

Proof. Take an element \(x\) of the union, and suppose it lies in exactly \(j \ge 1\) of the sets. On the right it is counted once for each nonempty \(S\) contained in those \(j\) indices, with sign \((-1)^{|S|+1}\). There are \(\binom{j}{i}\) such sets of size \(i\), so \(x\) is counted \[\sum_{i=1}^{j} (-1)^{i+1}\binom{j}{i} = 1 - \sum_{i=0}^{j}(-1)^i\binom{j}{i} = 1 - (1 - 1)^j = 1\] times. An element outside the union is counted zero times. So both sides count the same elements.

The complementary form is usually more convenient. If all the \(A_i\) lie in a universe \(U\), the number of elements in none of them is \[\Big|U \setminus \bigcup_i A_i\Big| = \sum_{S \subseteq [n]} (-1)^{|S|}|A_S|,\] where \(A_\emptyset = U\). Think of \(A_i\) as the set of objects having a bad property \(i\). We want the objects with no bad property; the formula needs only the numbers \(|A_S|\) of objects having all the bad properties in \(S\), and those are often easy to count because imposing properties is easy.

The symmetric case. If \(|A_S|\) depends only on \(|S|\), say \(|A_S| = N_k\) whenever \(|S| = k\), then the count of objects with no bad property is \(\sum_{k=0}^n (-1)^k \binom{n}{k} N_k\). All the applications below are of this kind.

Bonferroni inequalities

Truncating the alternating sum gives bounds. Carlo Emilio Bonferroni showed in 1936 that the partial sums alternately overshoot and undershoot: stopping after a positive term gives an upper bound for the union, after a negative term a lower bound. The first case is the union bound \(|\bigcup A_i| \le \sum|A_i|\), used constantly in probability and in lesson 12. The second is \(|\bigcup A_i| \ge \sum|A_i| - \sum_{i<j}|A_i \cap A_j|\). Proof sketch: an element in \(j\) sets is counted \(\sum_{i=1}^{m}(-1)^{i+1}\binom{j}{i}\) times by the partial sum up to size \(m\), and this equals \(1 - (-1)^m\binom{j-1}{m}\), which is at least 1 for odd \(m\) and at most 1 for even \(m\).

Counting with divisibility

How many integers from 1 to 1000 are divisible by none of 2, 3 and 5? Let \(A_p\) be the multiples of \(p\). The multiples of every prime in a set \(S\) are the multiples of the product, so \(|A_S| = \lfloor 1000/\prod_{p \in S} p \rfloor\). The count is \[1000 - (500 + 333 + 200) + (166 + 100 + 66) - 33 = 266.\] With floors removed, the answer would be \(1000(1 - \frac12)(1 - \frac13)(1 - \frac15) = 266.67\); the product appears because the alternating sum over subsets factors.

Euler's phi function. Let \(n = p_1^{a_1}\cdots p_r^{a_r}\), and count the integers from 1 to \(n\) coprime to \(n\), that is, divisible by none of the \(p_i\). Now the divisions are exact, so \[\varphi(n) = \sum_{S \subseteq [r]} (-1)^{|S|}\frac{n}{\prod_{i \in S}p_i} = n\prod_{i=1}^{r}\Big(1 - \frac{1}{p_i}\Big).\] MATH-351 proved this from multiplicativity; here it drops out of inclusion and exclusion directly. The same pattern with \(\mu(d)\), the Möbius function, gives \(\varphi(n) = \sum_{d \mid n}\mu(d)\,n/d\), and Gian-Carlo Rota showed in 1964 that inclusion–exclusion and Möbius inversion are two cases of a single principle on partially ordered sets.

Surjections

Count the functions from an \(n\)-set onto a \(k\)-set \(\{1, \ldots, k\}\). Let \(A_i\) be the functions that miss the value \(i\). A function missing every value in a set \(S\) of size \(j\) maps into the remaining \(k - j\) values, so \(|A_S| = (k - j)^n\). Therefore the number of surjections is \[\sum_{j=0}^{k}(-1)^j\binom{k}{j}(k - j)^n,\] and dividing by \(k!\) gives the explicit formula \[S(n, k) = \frac{1}{k!}\sum_{j=0}^{k}(-1)^j\binom{k}{j}(k - j)^n.\] For example \(S(5, 3) = \frac16(243 - 3 \cdot 32 + 3 \cdot 1) = \frac{150}{6} = 25\), matching the triangle of lesson 2. Taking \(k > n\) gives zero surjections, which yields the identity \(\sum_j (-1)^j\binom{k}{j}(k - j)^n = 0\) for \(n < k\), a fact about finite differences of polynomials.

Derangements

A derangement is a permutation with no fixed point. In 1708 Pierre Rémond de Montmort posed the problème des rencontres: if \(n\) cards numbered \(1\) to \(n\) are shuffled, what is the probability that no card is in its own position? The same question is told as the hat-check problem: \(n\) guests leave their hats, the hats are returned at random, and we want the chance that nobody gets their own hat.

Let \(A_i\) be the permutations fixing \(i\). Permutations fixing every element of a \(k\)-set \(S\) permute the other \(n - k\) freely, so \(|A_S| = (n - k)!\). The number of derangements is \[D_n = \sum_{k=0}^{n}(-1)^k\binom{n}{k}(n - k)! = n!\sum_{k=0}^{n}\frac{(-1)^k}{k!}.\] The sum is the beginning of the series for \(e^{-1}\). So the probability of a derangement tends to \(1/e \approx 0.3679\), and remarkably it is already within \(1/(n + 1)!\) of the limit. Since the tail of an alternating series with decreasing terms is smaller than its first term, \(|D_n - n!/e| < 1/(n + 1) < \frac12\), so \(D_n\) is the integer nearest to \(n!/e\) for \(n \ge 1\). The first values are \(D_1 = 0, D_2 = 1, D_3 = 2, D_4 = 9, D_5 = 44, D_6 = 265\).

Recurrences. Derangements also satisfy \(D_n = (n - 1)(D_{n-1} + D_{n-2})\). Proof: in a derangement \(\sigma\), the element \(n\) goes to some \(i \ne n\), in \(n - 1\) ways. If \(\sigma(i) = n\) as well, then \(i\) and \(n\) swap and the rest is a derangement of the other \(n - 2\) elements: \(D_{n-2}\) ways. If \(\sigma(i) \ne n\), let \(j\) be the element with \(\sigma(j) = n\), and define \(\tau\) on \(\{1, \ldots, n - 1\}\) by \(\tau(j) = i\) and \(\tau(x) = \sigma(x)\) otherwise. Then \(\tau\) is a derangement of \(n - 1\) elements, and \(\sigma\) is recovered from \(\tau\) and \(i\) by setting \(j = \tau^{-1}(i)\), \(\sigma(j) = n\) and \(\sigma(n) = i\): \(D_{n-1}\) ways for each \(i\). From this recurrence one can derive the simpler \(D_n = nD_{n-1} + (-1)^n\), by induction.

Partial derangements. The number of permutations of \(n\) with exactly \(r\) fixed points is \(\binom{n}{r}D_{n-r}\): choose the fixed points, then derange the rest. The expected number of fixed points of a random permutation is exactly 1 for every \(n\), by linearity: each element is fixed with probability \(1/n\). The distribution of the number of fixed points converges to a Poisson distribution with mean 1.

Forbidden positions and the ménage problem

Derangements forbid each element from one position. More generally, a permutation can be seen as a placement of \(n\) non-attacking rooks on an \(n \times n\) board, and some squares can be forbidden. If \(r_k\) is the number of ways to place \(k\) non-attacking rooks on the forbidden squares, inclusion and exclusion give the number of permutations avoiding all forbidden squares as \(\sum_k (-1)^k r_k (n - k)!\). For derangements the forbidden squares are the diagonal and \(r_k = \binom{n}{k}\).

The ménage problem, posed by Édouard Lucas in 1891, asks: in how many ways can \(n\) married couples sit at a round table with men and women alternating and nobody beside their partner? Seat the women first, in \(2 \cdot n!\) ways counting both sexes' positions; then each man is forbidden from two adjacent seats, which forms a cyclic band of \(2n\) forbidden squares. Placing \(k\) non-attacking rooks on that band is the same as choosing \(k\) non-adjacent squares from \(2n\) arranged in a circle, which can be done in \(\frac{2n}{2n-k}\binom{2n-k}{k}\) ways, as shown by Kaplansky in 1943. Hence the number of ways to seat the men is \[U_n = \sum_{k=0}^{n}(-1)^k\frac{2n}{2n-k}\binom{2n-k}{k}(n - k)!,\] Touchard's formula of 1934. The values for \(n = 3, 4, 5, 6\) are 1, 2, 13, 80.

from itertools import permutations
from math import comb, factorial, e

def derange_ie(n):
    return sum((-1) ** k * comb(n, k) * factorial(n - k) for k in range(n + 1))

def derange_brute(n):
    return sum(all(p[i] != i for i in range(n)) for p in permutations(range(n)))

D = [derange_ie(n) for n in range(13)]
print("D_n by inclusion-exclusion:", D)
print("brute force, n <= 8:", [derange_brute(n) for n in range(9)])
print("recurrence (n-1)(D[n-1]+D[n-2]) holds:", all(D[n] == (n - 1) * (D[n - 1] + D[n - 2]) for n in range(2, 13)))
print("D_n = n D[n-1] + (-1)^n holds:", all(D[n] == n * D[n - 1] + (-1) ** n for n in range(1, 13)))
print("D_n is nearest integer to n!/e:", all(D[n] == round(factorial(n) / e) for n in range(1, 13)))
for n in [4, 8, 12]:
    print(f"P(no fixed point), n={n}: {D[n] / factorial(n):.7f}   1/e = {1 / e:.7f}")

def surjections(n, k):
    return sum((-1) ** j * comb(k, j) * (k - j) ** n for j in range(k + 1))
print("surjections 6 -> 3:", surjections(6, 3), " S(6,3) =", surjections(6, 3) // factorial(3))
print("surjections 4 -> 5 (should be 0):", surjections(4, 5))

def none_divisible(N, primes):
    total = 0
    for mask in range(1 << len(primes)):
        prod, bits = 1, 0
        for i, p in enumerate(primes):
            if mask >> i & 1:
                prod *= p; bits += 1
        total += (-1) ** bits * (N // prod)
    return total
print("1..1000 divisible by none of 2, 3, 5:", none_divisible(1000, [2, 3, 5]),
      " direct:", sum(all(x % p for p in (2, 3, 5)) for x in range(1, 1001)))

# Bonferroni: partial sums for the union A2 U A3 U A5 U A7 inside 1..1000
primes = [2, 3, 5, 7]
union = sum(any(x % p == 0 for p in primes) for x in range(1, 1001))
partial = 0
for size in range(1, 5):
    term = 0
    for mask in range(1, 16):
        if bin(mask).count("1") == size:
            prod = 1
            for i in range(4):
                if mask >> i & 1:
                    prod *= primes[i]
            term += 1000 // prod
    partial += (-1) ** (size + 1) * term
    print(f"  partial sum through size {size}: {partial}  ({'upper' if size % 2 else 'lower'} bound for {union})")

def menage_formula(n):
    return sum((-1) ** k * 2 * n * comb(2 * n - k, k) // (2 * n - k) * factorial(n - k) for k in range(n + 1))

def menage_brute(n):
    return sum(all(p[i] != i and p[i] != (i + 1) % n for i in range(n)) for p in permutations(range(n)))
print("menage numbers, formula n=3..9:", [menage_formula(n) for n in range(3, 10)])
print("menage numbers, brute force n=3..8:", [menage_brute(n) for n in range(3, 9)])

D_n by inclusion-exclusion: [1, 0, 1, 2, 9, 44, 265, 1854, 14833, 133496, 1334961, 14684570, 176214841]
brute force, n <= 8: [1, 0, 1, 2, 9, 44, 265, 1854, 14833]
recurrence (n-1)(D[n-1]+D[n-2]) holds: True
D_n = n D[n-1] + (-1)^n holds: True
D_n is nearest integer to n!/e: True
P(no fixed point), n=4: 0.3750000   1/e = 0.3678794
P(no fixed point), n=8: 0.3678819   1/e = 0.3678794
P(no fixed point), n=12: 0.3678794   1/e = 0.3678794
surjections 6 -> 3: 540  S(6,3) = 90
surjections 4 -> 5 (should be 0): 0
1..1000 divisible by none of 2, 3, 5: 266  direct: 266
  partial sum through size 1: 1175  (upper bound for 772)
  partial sum through size 2: 697  (lower bound for 772)
  partial sum through size 3: 776  (upper bound for 772)
  partial sum through size 4: 772  (lower bound for 772)
menage numbers, formula n=3..9: [1, 2, 13, 80, 579, 4738, 43387]
menage numbers, brute force n=3..8: [1, 2, 13, 80, 579, 4738]

The derangement probabilities agree with \(1/e\) to seven decimal places already at \(n = 12\). The Bonferroni partial sums alternate above and below the true size of the union, closing in on it, and the ménage formula agrees with a direct count of the permutations that avoid two forbidden positions in each row.