40.01.02 · combinatorics / enumeration-generating-functions

Inclusion-Exclusion and the Sieve

shipped3 tiersLean: none

Anchor (Master): Stanley 2012 *Enumerative Combinatorics, Volume 1* 2e §2.1-2.7 and Notes (inclusion-exclusion as Möbius inversion on the Boolean lattice, the involution principle, permanents and rook polynomials, sign-reversing involutions); Aigner 2007 *A Course in Enumeration* (Springer) §5; Rota 1964 *Amer. Math. Monthly* / *Z. Wahrscheinlichkeitstheorie* 2 (the Möbius-function programme placing the sieve inside poset theory); Bonferroni 1936 *Pubbl. R. Ist. Sup. Sci. Econ. Comm. Firenze* (the partial-sum inequalities)

Intuition Beginner

Suppose you want to count the students in a class who play neither soccer nor chess. You know how many play soccer, how many play chess, and how many play both. A first guess is to take the whole class and subtract the soccer players and the chess players. That over-corrects: anyone who plays both sports got subtracted twice, once in each list, even though they are a single person. To repair the count you add the both-players back in once. Subtract the two single lists, add back the overlap — that is the whole idea in miniature.

The principle of inclusion-exclusion is this repair carried out for any number of overlapping lists. You include everything, then exclude the pairwise overlaps you double-counted, then include the triple overlaps you over-excluded, and so on, with the signs alternating plus and minus. Each element of the universe gets counted exactly the right number of times once all the corrections are in. The alternating sum is not a clever trick pulled from nowhere; it is the unique bookkeeping that makes every element's net count come out to one if it should be counted and zero if it should not.

People reach for this principle whenever a set is easy to describe by the bad properties it should avoid rather than by the good properties it should have. "Arrangements where no one sits in their own seat", "numbers below a million sharing no factor with it", "ways to seat couples so no husband sits beside his wife" — each is a count of objects avoiding a list of forbidden conditions. Counting the avoiders directly is hard; counting how many objects have at least a given batch of forbidden conditions is easy, and the sieve assembles those easy counts into the hard one.

The pattern you should carry forward is the sieve: a fine-grained subtract-and-restore that strains out exactly the elements failing none of the conditions. The same alternating-sign signature reappears later as the Möbius function on the lattice of subsets, the deepest reason the signs are what they are.

Visual Beginner

Picture three overlapping circles in a rectangle: the rectangle is everyone, the circles are the soccer, chess, and tennis players. To count people inside at least one circle, add the three circle sizes, subtract the three pairwise lens-shaped overlaps, then add back the central region where all three meet.

The table tracks how many times a person in each region is counted as the corrections accumulate. A person in exactly one circle is counted once and never touched again. A person in exactly two circles is added twice, then subtracted once — net one. A person in all three is added three times, subtracted three times, then added once — net one.

region	added by singles	removed by pairs	added by triple	net
in one circle	$1$	$0$	$0$	$1$
in two circles	$2$	$1$	$0$	$1$
in all three	$3$	$3$	$1$	$1$
in no circle	$0$	$0$	$0$	$0$

Every row in the union nets to one, and the outsiders net to zero. That last column is the entire content of the principle: the alternating sum is the unique weighting that scores each element by whether it belongs.

Worked example Beginner

Count the derangements of three guests: the seatings of guests $1, 2, 3$ into chairs $1, 2, 3$ so that no guest sits in the chair matching their number. We do it by listing, then by the sieve.

Step 1. List all $3! = 6$ seatings, writing each as the chairs taken by guests $1, 2, 3$ in order. They are $123, 132, 213, 231, 312, 321$ . A seating is a derangement when no position holds its own number.

Step 2. Strike the bad ones. $123$ fixes all three. $132$ fixes guest $1$ . $213$ fixes guest $3$ . $321$ fixes guest $2$ . That leaves $231$ and $312$ , where every guest avoids their own chair. So there are $2$ derangements by direct count.

Step 3. Now the sieve. Start from all $6$ seatings. Subtract those fixing at least one chosen guest. Fixing guest $1$ leaves the other two free: $2! = 2$ seatings; same for guests $2$ and $3$ , giving $3 \times 2 = 6$ to subtract. But seatings fixing two guests got subtracted twice, so add them back: fixing guests $1$ and $2$ forces guest $3$ too, giving $1$ seating, and there are $3$ such pairs, so add $3$ . Finally subtract the one seating fixing all three.

Step 4. Assemble: $6 - 6 + 3 - 1 = 2$ . The sieve agrees with the list.

What this tells us: the alternating sum $6 - 6 + 3 - 1$ counts "at least one fixed guest" with the right multiplicities, and subtracting it from the total leaves exactly the seatings fixing nobody. The same recipe with $n$ guests gives $n! - (1 n) (n - 1)! + (2 n) (n - 2)! - \dots$ , which we meet again in the formal sections.

Check your understanding Beginner

Formal definition Intermediate+

Let $U$ be a finite universe and let $A_{1}, \dots, A_{n} \subseteq U$ . For a subset $T \subseteq [n] = {1, \dots, n}$ write $A_{T} = ⋂_{i \in T} A_{i}$ with the convention $A_{\emptyset} = U$ , and set $N_{\supseteq T} = ∣ A_{T} ∣$ , the number of elements lying in at least the sets indexed by $T$ .

Definition (inclusion-exclusion, union form). The cardinality of the union is the alternating sum $$ \Bigl|\bigcup_{i=1}^{n} A_i\Bigr| = \sum_{\varnothing \neq T \subseteq [n]} (-1)^{|T|+1},|A_T| = \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 . $$

Definition (complementary form). The number of elements of $U$ lying in none of the $A_{i}$ — equivalently with none of the corresponding properties — is $$ \Bigl|U \setminus \bigcup_{i=1}^n A_i\Bigr| = \sum_{T \subseteq [n]} (-1)^{|T|},N_{\supseteq T} = N_{\supseteq \varnothing} - \sum_i N_{\supseteq {i}} + \sum_{i<j} N_{\supseteq {i,j}} - \cdots . $$ This is the sieve formula: it strains $U$ down to the elements satisfying none of the listed conditions.

Definition (property-count refinement). Index by properties $P_{1}, \dots, P_{n}$ and let $N_{k} = \sum_{∣ T ∣ = k} N_{\supseteq T}$ be the sum of $(k n)$ intersection counts, so $N_{k}$ tallies, with multiplicity, the elements satisfying at least the properties in some $k$ -subset. Write $E_{m}$ for the number of elements satisfying exactly $m$ of the properties. The complementary form is the case $E_{0} = \sum_{k} (- 1)^{k} N_{k}$ ; the general refinement is $$ E_m = \sum_{k=m}^{n} (-1)^{k-m}\binom{k}{m} N_k , $$ the Sylvester-Whitney formula, and the truncations of these alternating sums are the Bonferroni inequalities ^{[Bonferroni 1936]}.

Definition (Boolean-lattice viewpoint). The subsets of $[n]$ ordered by inclusion form the Boolean lattice $2^{[n]}$ . On any locally finite poset the zeta function $ζ (S, T) = [S \subseteq T]$ has a convolution inverse, the Möbius function $μ$ ; for $2^{[n]}$ one computes $μ (S, T) = (- 1)^{∣ T ∖ S ∣}$ when $S \subseteq T$ and $0$ otherwise. The sieve is the assertion that the map $f (T) = N_{\supseteq T}$ and the map $g (T) = (count of elements satisfying exactly the properties in T)$ are related by $f = ζ * g$ , so $g = μ * f$ ; reading off $g (\emptyset)$ recovers $E_{0}$ . The general theory on an arbitrary poset is developed in 40.02.02; this unit owns the set-theoretic instance.

Counterexamples to common slips Intermediate+

" $N_{k}$ is the number of elements with exactly $k$ properties." It is not. $N_{k} = \sum_{∣ T ∣ = k} N_{\supseteq T}$ counts pairs (element, $k$ -subset of its properties), so an element with $j \geq k$ properties is counted $(k j)$ times. The exactly- $k$ count is $E_{k}$ , recovered from the $N_{k}$ by the Sylvester-Whitney sum, not by reading $N_{k}$ directly.
"Truncating the sieve early gives an approximation of unknown sign." The Bonferroni inequalities pin the sign: stopping the alternating sum for a union after a $+$ term gives an upper bound, after a $-$ term a lower bound. The error is controlled, not merely small.
"Inclusion-exclusion needs the $A_{i}$ to be disjoint or nested." It holds for arbitrary overlaps; the alternating signs exist precisely to handle arbitrary multiplicities of overlap. Disjointness collapses every intersection term to zero and reduces the formula to the sum rule.
"The signs $(- 1)^{∣ T ∣}$ are a convention one could flip." They are forced: $(- 1)^{∣ T ∣}$ is the Möbius function of the Boolean lattice, the unique inverse of the zeta function, so any other sign pattern fails to invert the over-counting.

Key theorem with proof Intermediate+

The signature theorem is the sieve formula itself, proved by the indicator-function identity that makes every element's net contribution equal one or zero.

Theorem (inclusion-exclusion / sieve). With notation as above, $$ \Bigl|U \setminus \bigcup_{i=1}^{n} A_i\Bigr| = \sum_{T \subseteq [n]} (-1)^{|T|},|A_T|, \qquad \Bigl|\bigcup_{i=1}^n A_i\Bigr| = \sum_{\varnothing \neq T \subseteq [n]} (-1)^{|T|+1},|A_T| . $$

Proof. Fix an element $x \in U$ and let $P (x) = {i \in [n] : x \in A_{i}}$ be the set of indices whose sets contain $x$ ; write $r = ∣ P (x) ∣$ . We show that $x$ contributes the value $[r = 0]$ to the right-hand side of the first identity, where $[\cdot]$ is $1$ when the bracketed statement holds and $0$ otherwise; summing over $x$ then gives the count of elements in no $A_{i}$ .

The element $x$ lies in $A_{T} = ⋂_{i \in T} A_{i}$ exactly when $T \subseteq P (x)$ . Its total contribution to $\sum_{T} (- 1)^{∣ T ∣} ∣ A_{T} ∣$ is therefore $$ \sum_{T \subseteq P(x)} (-1)^{|T|} = \sum_{k=0}^{r} \binom{r}{k}(-1)^k = (1 - 1)^r = [r = 0], $$ using the binomial theorem $(1 + y)^{r} = \sum_{k} (k r) y^{k}$ at $y = - 1$ , which vanishes for $r \geq 1$ and equals $1$ for $r = 0$ . Hence each $x \in / ⋃_{i} A_{i}$ contributes $1$ and each $x \in ⋃_{i} A_{i}$ contributes $0$ , so the right-hand side counts $∣ U ∖ ⋃_{i} A_{i} ∣$ . Subtracting from $∣ U ∣ = N_{\supseteq \emptyset}$ and rearranging the $T = \emptyset$ term gives the union form. $□$

Corollary (derangements). The number of permutations of $[n]$ with no fixed point is $D_{n} = \sum_{k = 0}^{n} (- 1)^{k} (k n) (n - k)! = n! \sum_{k = 0}^{n} \frac{( - 1 ) ^{k}}{k !}$ . Indeed, let $A_{i}$ be the permutations fixing $i$ ; an intersection $A_{T}$ over a $k$ -set $T$ fixes those $k$ points and permutes the rest freely, so $∣ A_{T} ∣ = (n - k)!$ and there are $(k n)$ such $T$ . The sieve gives $D_{n} = \sum_{k} (- 1)^{k} (k n) (n - k)!$ , and $(k n) (n - k)! = n! / k!$ yields the second form. As $n \to \infty$ the sum converges to $n! e^{- 1}$ , so a uniformly random permutation has no fixed point with limiting probability $1/ e$ .

Bridge. This theorem is the foundational reason a count of "objects avoiding all of a list of properties" is always within reach: the alternating sum is the only weighting whose per-element total is the indicator $[r = 0]$ , and the binomial collapse $(1 - 1)^{r}$ is exactly the Boolean-lattice shadow of the more general Möbius inversion. The sieve builds toward the poset Möbius theory, where $(- 1)^{∣ T ∣}$ is replaced by $μ (S, T)$ on an arbitrary locally finite poset; this is exactly the statement that $ζ$ and $μ$ are mutually inverse in the incidence algebra, and the Boolean case generalises to chains, divisor lattices, and partition lattices alike. Putting these together, the derangement corollary is the prototype that appears again in the ménage problem and in every restricted-position count, where the forbidden positions index the properties and the central insight is that the permanent of a board complement is a single sieve in disguise. The bridge is that one indicator identity, summed over a universe, underwrites derangements, the totient, surjections, and the rook-polynomial machinery as a single mechanism.

Exercises Intermediate+

Exercise 3 (medium, symbolic).

Derive the Euler totient formula $φ (N) = N \prod_{p ∣ N} (1 - \frac{1}{p})$ from the sieve, where the product runs over the distinct primes dividing $N$ .

Hint

Let $A_{p}$ be the multiples of $p$ in ${1, \dots, N}$ . Then $∣ A_{p_{1}} \cap \dots \cap A_{p_{j}} ∣ = N / (p_{1} \dots p_{j})$ . Apply the complementary form and factor.

Answer

Let $p_{1}, \dots, p_{r}$ be the distinct primes dividing $N$ and let $A_{i}$ be the multiples of $p_{i}$ in ${1, \dots, N}$ . For a subset $T \subseteq [r]$ , the intersection $A_{T}$ is the multiples of $\prod_{i \in T} p_{i}$ , of which there are $N / \prod_{i \in T} p_{i}$ since $\prod_{i \in T} p_{i} ∣ N$ . The complementary form gives $$ \varphi(N) = \sum_{T \subseteq [r]} (-1)^{|T|}\frac{N}{\prod_{i\in T}p_i} = N\sum_{T}\prod_{i\in T}\frac{-1}{p_i} = N\prod_{i=1}^r\Bigl(1 - \frac{1}{p_i}\Bigr), $$ the last step expanding the product $\prod_{i} (1 - 1/ p_{i})$ term by term and matching each monomial to a subset $T$ . Rubric: full credit for the intersection count, the complementary-form sum, and the factorisation of the alternating sum into the Euler product.

Exercise 4 (medium, symbolic).

Prove the surjection count $Surj (n, k) = \sum_{j = 0}^{k} (- 1)^{j} (j k) (k - j)^{n}$ by inclusion-exclusion on the codomain.

Hint

Let $A_{i}$ be the functions $[n] \to [k]$ that miss the value $i$ . A surjection is a function in none of the $A_{i}$ .

Answer

Among all $k^{n}$ functions $f : [n] \to [k]$ , let $A_{i}$ be those whose image avoids $i$ . For a $j$ -subset $T \subseteq [k]$ , the functions in $A_{T}$ avoid every value of $T$ , hence land in the remaining $k - j$ values, so $∣ A_{T} ∣ = (k - j)^{n}$ , and there are $(j k)$ such $T$ . A function is a surjection exactly when it lies in no $A_{i}$ , so the complementary form gives $Surj (n, k) = \sum_{j = 0}^{k} (- 1)^{j} (j k) (k - j)^{n}$ . Dividing by $k!$ recovers the Stirling number $S (n, k)$ , tying this to the surjective cell of the twelvefold way 40.01.01. Rubric: full credit for the intersection count $(k - j)^{n}$ , the $(j k)$ multiplicity, and the complementary-form assembly.

Exercise 6 (medium, symbolic).

Prove the Sylvester-Whitney formula $E_{m} = \sum_{k = m}^{n} (- 1)^{k - m} (m k) N_{k}$ , where $E_{m}$ counts elements with exactly $m$ properties and $N_{k} = \sum_{∣ T ∣ = k} N_{\supseteq T}$ .

Hint

An element with exactly $j$ properties is counted $(k j)$ times in $N_{k}$ . Compute the coefficient of such an element on the right side and show it equals $[j = m]$ .

Answer

Fix an element with exactly $j$ properties. It contributes $(k j)$ to $N_{k}$ , since it lies in $A_{T}$ for each $k$ -subset $T$ of its $j$ properties. Its total coefficient on the right side is $$ \sum_{k=m}^{n}(-1)^{k-m}\binom{k}{m}\binom{j}{k} = \binom{j}{m}\sum_{k=m}^{j}(-1)^{k-m}\binom{j-m}{k-m} = \binom{j}{m}(1-1)^{j-m} = \binom{j}{m}[j=m], $$ using the subset-of-a-subset identity $(m k) (k j) = (m j) (k - m j - m)$ and the binomial collapse. The bracket is $1$ exactly when $j = m$ (where $(m m) = 1$ ) and $0$ otherwise, so the right side counts precisely the elements with exactly $m$ properties, namely $E_{m}$ . Rubric: full credit for the $(k j)$ multiplicity, the trinomial-revision identity, and the $(1 - 1)^{j - m}$ collapse to $[j = m]$ .

Exercise 7 (hard, symbolic).

Prove the even/odd Bonferroni inequalities for a union: for every $0 \leq ℓ \leq n$ , $$ \sum_{k=1}^{2\ell}(-1)^{k+1}S_k ;\leq; \Bigl|\bigcup_i A_i\Bigr| ;\leq; \sum_{k=1}^{2\ell+1}(-1)^{k+1}S_k, \qquad S_k = \sum_{|T|=k}|A_T|, $$ whenever the truncation indices do not exceed $n$ .

Hint

Fix $x$ in $r \geq 1$ of the sets. Its contribution to the partial sum $\sum_{k = 1}^{m} (- 1)^{k + 1} S_{k}$ is $\sum_{k = 1}^{m} (- 1)^{k + 1} (k r)$ . Compare this partial alternating binomial sum to $1$ .

Answer

Each $x$ lying in exactly $r \geq 1$ sets contributes $\sum_{k = 1}^{m} (- 1)^{k + 1} (k r)$ to the truncated sum $\sum_{k = 1}^{m} (- 1)^{k + 1} S_{k}$ , while its true contribution to the union is $1$ . Set $c_{m} (r) = \sum_{k = 0}^{m} (- 1)^{k} (k r)$ ; the standard identity $c_{m} (r) = (- 1)^{m} (m r - 1)$ (provable by induction on $m$ using Pascal's rule) gives $\sum_{k = 1}^{m} (- 1)^{k + 1} (k r) = 1 - c_{m} (r) = 1 - (- 1)^{m} (m r - 1)$ . For $m = 2 ℓ$ even this is $1 - (2 ℓ r - 1) \leq 1$ , and for $m = 2 ℓ + 1$ odd it is $1 + (2 ℓ + 1 r - 1) \geq 1$ . Summing over all $x$ in the union: the even truncation undercounts every element's contribution, giving a lower bound, and the odd truncation overcounts, giving an upper bound. Elements in no set contribute $0$ on both sides. This is the Bonferroni pair. Rubric: full credit for the per-element binomial partial sum, the closed form $(- 1)^{m} (m r - 1)$ , and the sign analysis of even versus odd $m$ .

Exercise 8 (hard, symbolic).

The principle of restricted positions: given a board $B \subseteq [n] \times [n]$ of forbidden cells, the number of permutations $σ$ of $[n]$ with $(i, σ (i)) \in / B$ for all $i$ equals $\sum_{k = 0}^{n} (- 1)^{k} r_{k} (n - k)!$ , where $r_{k}$ is the number of ways to place $k$ non-attacking rooks on $B$ . Prove this from inclusion-exclusion.

Hint

Let property $i$ of a permutation be " $(i, σ (i)) \in B$ ". A set of $k$ permutations-with-properties corresponds to $k$ forbidden cells, no two in the same row or column — that is, $k$ non-attacking rooks. The remaining $n - k$ values are free.

Answer

For a permutation $σ$ let property $P_{i}$ hold when $(i, σ (i)) \in B$ , so the permutations to be counted satisfy none of the $P_{i}$ . For a $k$ -subset $S$ of rows, $N_{\supseteq S}$ counts permutations whose graph meets $B$ in (at least) the rows of $S$ ; specifying which forbidden cell is hit in each row of $S$ requires choosing $k$ cells of $B$ , one per row of $S$ , with distinct columns — a placement of $k$ non-attacking rooks on $B$ occupying the rows $S$ — after which the remaining $n - k$ rows take the remaining $n - k$ columns in any of $(n - k)!$ ways. Summing $N_{\supseteq S}$ over all $S$ of size $k$ assembles every non-attacking $k$ -rook placement on $B$ exactly once, so $N_{k} = r_{k} (n - k)!$ . The complementary form $E_{0} = \sum_{k} (- 1)^{k} N_{k}$ then gives $\sum_{k = 0}^{n} (- 1)^{k} r_{k} (n - k)!$ . The rook numbers $r_{k}$ are the coefficients of the rook polynomial $R_{B} (x) = \sum_{k} r_{k} x^{k}$ , and this count is the permanent of the $0 - 1$ complement matrix of $B$ . Rubric: full credit for identifying properties with forbidden cells, the non-attacking-rook interpretation of $N_{k}$ , the factor $(n - k)!$ , and the complementary-form assembly.

Advanced results Master

The sieve is the degree-zero case of Möbius inversion; its depth emerges once the index set carries a lattice structure, once the alternating sum is read as a permanent, and once the cancellation is made bijective by an involution.

Theorem 1 (sieve as Boolean Möbius inversion). On the Boolean lattice $2^{[n]}$ the incidence algebra carries the zeta function $ζ (S, T) = [S \subseteq T]$ and its convolution inverse $μ (S, T) = (- 1)^{∣ T ∣ - ∣ S ∣} [S \subseteq T]$ . For functions $f, g : 2^{[n]} \to Z$ the inversion $f (S) = \sum_{T \supseteq S} g (T) ⟺ g (S) = \sum_{T \supseteq S} (- 1)^{∣ T ∣ - ∣ S ∣} f (T)$ holds, and the complementary sieve is the case $S = \emptyset$ with $f (T) = N_{\supseteq T}$ , $g (\emptyset) = E_{0}$ ^{[Aigner 2007]}. The arithmetic Möbius function on the divisor lattice 21.11.01 and the set-theoretic sign $(- 1)^{∣ T ∣}$ are two specialisations of the one poset Möbius function developed in 40.02.02; this unit owns the set-theoretic sieve, the divisor case is owned there, and the analytic sieve of 21.14.01 is the number-theoretic refinement that controls error terms rather than counting exactly.

Theorem 2 (the ménage problem). The number of ways to seat $n$ married couples around a circular table, men and women alternating, with no wife adjacent to her own husband, is $$ M_n = \sum_{k=0}^{n} (-1)^k \frac{2n}{2n-k}\binom{2n-k}{k}(n-k)! . $$ The factor $\frac{2 n}{2 n - k} (k 2 n - k)$ is the rook number $r_{k}$ of the $2 n$ -cell board consisting of the two diagonals encoding the forbidden husband-left and husband-right adjacencies; counting non-attacking rook placements on a circular two-diagonal board is the Touchard-Kaplansky lemma. The ménage count is the headline application of the principle of restricted positions, and Wyman-Moser made the asymptotic $M_{n} \sim n! e^{- 2} (2 n)$ precise.

Theorem 3 (permanents and restricted positions). For a $0 - 1$ matrix $A = (a_{ij})$ , the permanent $per A = \sum_{σ \in S_{n}} \prod_{i} a_{iσ (i)}$ counts the permutations $σ$ with $a_{iσ (i)} = 1$ for all $i$ . Taking $A$ to be the complement of the forbidden board $B$ , the count of placements avoiding $B$ is $per (J - C_{B})$ , where $J$ is all-ones and $C_{B}$ the indicator of $B$ , and the inclusion-exclusion expansion of this permanent is exactly $\sum_{k} (- 1)^{k} r_{k} (n - k)!$ of Exercise 8. The permanent is $# P$ -hard to compute in general (Valiant 1979), so the sieve trades an intractable permanent for the rook polynomial of $B$ , tractable when $B$ is sparse or structured.

Theorem 4 (the involution principle). The cancellation $\sum_{T \subseteq P (x)} (- 1)^{∣ T ∣} = [P (x) = \emptyset]$ is realised bijectively: fixing any element $j^{⋆} \in P (x)$ (when $P (x) \neq = \emptyset$ ), the map $T \mapsto T △ {j^{⋆}}$ is a sign-reversing involution on the subsets of $P (x)$ with no fixed points, pairing each $T$ with one of opposite parity and equal weight. Garsia and Milne's involution principle generalises this: every inclusion-exclusion identity with non-negative refined counts can be upgraded to an explicit weight-preserving bijection between the surviving objects, turning a signed identity into a combinatorial one. This is the mechanism behind Franklin-style involutive proofs and the bijective proofs of restricted-partition identities.

Theorem 5 (Bonferroni inequalities, refined). The truncated sieve sums bracket the true count: for the union, partial sums ending on $+$ overestimate and those ending on $-$ underestimate, and analogously $\sum_{k = m}^{M} (- 1)^{k - m} (m k) N_{k}$ brackets $E_{m}$ as $M$ ranges over the parities. These inequalities make inclusion-exclusion usable as an estimation tool when the full alternating sum is intractable, and in probability they yield the Bonferroni and Galambos bounds on $P (⋃ A_{i})$ used throughout the second-moment method ^{[Bonferroni 1936]}.

Synthesis. The principle of inclusion-exclusion is the foundational reason a single mechanism underlies derangements, the totient, surjections, the ménage seating, and every restricted-position count: each is a sieve $E_{0} = \sum_{T} (- 1)^{∣ T ∣} N_{\supseteq T}$ for a suitable family of properties, and the alternating signs are not chosen but forced, being the Möbius function $(- 1)^{∣ T ∣}$ of the Boolean lattice. The central insight is that this Boolean Möbius function is one instance of the poset Möbius function of 40.02.02, so the set-theoretic sieve, the arithmetic Möbius inversion of 21.11.01, and the analytic sieves of 21.14.01 are the same inversion read on the subset lattice, the divisor lattice, and the integers with error control respectively. Putting these together, the permanent formulation shows the sieve trades a $# P$ -hard count for the rook polynomial, the involution principle shows the signed cancellation is dual to an explicit bijection, and the Bonferroni truncations show the alternating sum degrades gracefully into two-sided bounds. This is exactly the bridge that builds toward analytic combinatorics and probabilistic sieve theory: the elementary subtract-and-restore of the Beginner tier generalises to the full incidence-algebra inversion that organises enumeration, where each refinement — exactly- $m$ , bounded truncation, bijective realisation, permanent evaluation — is a face of the one Möbius identity.

Full proof set Master

Proposition 1 (sieve via the indicator identity). For finite $A_{1}, \dots, A_{n} \subseteq U$ , the number of elements in none of the $A_{i}$ is $\sum_{T \subseteq [n]} (- 1)^{∣ T ∣} ∣ A_{T} ∣$ , with $A_{\emptyset} = U$ .

Proof. Write $1_{S}$ for the indicator function of a set $S$ . For each $x \in U$ with property set $P (x) = {i : x \in A_{i}}$ of size $r$ , the contribution of $x$ to $\sum_{T} (- 1)^{∣ T ∣} ∣ A_{T} ∣ = \sum_{T} (- 1)^{∣ T ∣} \sum_{x} 1_{A_{T}} (x)$ is $\sum_{T \subseteq P (x)} (- 1)^{∣ T ∣}$ , since $x \in A_{T}$ precisely when $T \subseteq P (x)$ . This inner sum is $\sum_{k = 0}^{r} (k r) (- 1)^{k} = (1 - 1)^{r}$ , which equals $1$ if $r = 0$ and $0$ if $r \geq 1$ . Summing over $x$ counts exactly the $x$ with $P (x) = \emptyset$ , the elements in no $A_{i}$ . $□$

Proposition 2 (derangement closed form and limit). $D_{n} = \sum_{k = 0}^{n} (- 1)^{k} (k n) (n - k)! = n! \sum_{k = 0}^{n} \frac{( - 1 ) ^{k}}{k !}$ , and $D_{n} / n! \to e^{- 1}$ .

Proof. Let $A_{i}$ be the permutations of $[n]$ fixing $i$ . For $∣ T ∣ = k$ , $A_{T}$ fixes the $k$ points of $T$ and permutes the complementary $n - k$ points arbitrarily, so $∣ A_{T} ∣ = (n - k)!$ ; there are $(k n)$ subsets of size $k$ . Proposition 1 gives $D_{n} = \sum_{k} (- 1)^{k} (k n) (n - k)!$ . Since $(k n) (n - k)! = \frac{n !}{k ! ( n - k )!} (n - k)! = \frac{n !}{k !}$ , this is $n! \sum_{k} (- 1)^{k} / k!$ . The sum is the degree- $n$ truncation of the Taylor series of $e^{- 1}$ , whose tail $\sum_{k > n} (- 1)^{k} / k!$ is bounded by $1/ (n + 1)!$ in absolute value, so $D_{n} / n! \to \sum_{k \geq 0} (- 1)^{k} / k! = e^{- 1}$ . $□$

Proposition 3 (Euler totient as a sieve). For $N \geq 1$ with distinct prime divisors $p_{1}, \dots, p_{r}$ , $φ (N) = N \prod_{i = 1}^{r} (1 - 1/ p_{i})$ .

Proof. Let $A_{i} = {m \in [N] : p_{i} ∣ m}$ , so $∣ A_{i} ∣ = N / p_{i}$ and, for $T \subseteq [r]$ , $∣ A_{T} ∣ = N / \prod_{i \in T} p_{i}$ because the $p_{i}$ are distinct primes and $\prod_{i \in T} p_{i} ∣ N$ . The integers coprime to $N$ are exactly those in no $A_{i}$ , so Proposition 1 gives $$ \varphi(N) = \sum_{T\subseteq[r]}(-1)^{|T|}\frac{N}{\prod_{i\in T}p_i} = N\prod_{i=1}^r\Bigl(1 - \frac{1}{p_i}\Bigr), $$ the product expanding to the alternating sum over subsets $T$ . This recovers multiplicativity of $φ$ and the divisor identity $\sum_{d ∣ N} φ (d) = N$ , both owned downstream by 21.11.01. $□$

Proposition 4 (restricted positions and the rook polynomial). For a forbidden board $B \subseteq [n] \times [n]$ with rook numbers $r_{k}$ , the number of permutations avoiding $B$ is $\sum_{k = 0}^{n} (- 1)^{k} r_{k} (n - k)!$ .

Proof. Let property $P_{i}$ of a permutation $σ$ hold when $(i, σ (i)) \in B$ . The permutations avoiding $B$ satisfy none of the $P_{i}$ . For $N_{k} = \sum_{∣ S ∣ = k} N_{\supseteq S}$ , a term $N_{\supseteq S}$ counts permutations whose graph contains a chosen forbidden cell in each row of $S$ ; the chosen cells lie in distinct rows (the rows of $S$ ) and distinct columns (since $σ$ is a bijection), so they form a non-attacking $k$ -rook placement on $B$ , and the remaining $n - k$ rows are filled by a bijection onto the remaining $n - k$ columns in $(n - k)!$ ways. Each non-attacking $k$ -rook placement arises from exactly one choice of $S$ (the occupied rows), so $N_{k} = r_{k} (n - k)!$ . Proposition 1 in the form $E_{0} = \sum_{k} (- 1)^{k} N_{k}$ yields $\sum_{k} (- 1)^{k} r_{k} (n - k)!$ . When $B$ is the union of two diagonals on the seating cycle, $r_{k} = \frac{2 n}{2 n - k} (k 2 n - k)$ by the Touchard-Kaplansky count, giving the ménage number $M_{n}$ . $□$

Connections Master

The alternating sign $(- 1)^{∣ T ∣}$ that drives the sieve is the Möbius function of the Boolean lattice $2^{[n]}$ , and inclusion-exclusion is precisely Möbius inversion on that poset. The general theory — the incidence algebra of a locally finite poset, the zeta function and its inverse $μ$ , and inversion on chains, divisor lattices, and partition lattices — is the co-produced unit 40.02.02, which this sieve is the elementary base case of. The foundational reason the signs invert the over-counting is that $μ$ is the unique convolution inverse of $ζ$ .
The arithmetic Möbius function and Möbius inversion over the divisor lattice are owned by 21.11.01: the totient computation of this unit is the set-theoretic sieve specialised to the prime-divisor properties, whereas 21.11.01 develops the same inversion as a statement about Dirichlet convolution and multiplicative functions. The boundary is deliberate — this unit owns the finite set-theoretic sieve, that unit owns the number-theoretic Dirichlet form.
The analytic sieves of number theory — the Eratosthenes-Legendre sieve, Brun's sieve, and the large sieve — are the asymptotic descendants developed in 21.14.01, where the exact alternating sum is truncated and its error term estimated rather than evaluated. The Bonferroni inequalities of this unit are the elementary truncation bounds that those analytic sieves sharpen; this unit counts exactly, that unit controls error terms when exact evaluation is intractable.
The surjection count $\sum_{j} (- 1)^{j} (j k) (k - j)^{n}$ recovered here by sieving the codomain is the inclusion-exclusion half of the twelvefold way's signature theorem 40.01.01, where it was paired with the bijective identity $Surj (n, k) = k! S (n, k)$ . This unit isolates and generalises the sieve half of that argument into the abstract principle.

Historical & philosophical context Master

The principle was stated by Abraham de Moivre in his Doctrine of Chances (1718) and, in the form of the derangement count, by Pierre Rémond de Montmort, who in 1708 posed and solved the problème des rencontres — the matching game later named after him — obtaining $D_{n} / n! \to 1/ e$ . Nicholas Bernoulli and Euler returned to the derangement problem independently; Euler's 1779 treatment of the problème des ménages (in the form studied by Édouard Lucas in 1891 and solved by Jacques Touchard in 1934) established the restricted-position circle of ideas. James Joseph Sylvester gave the principle its general "exactly $m$ " form in the 1880s, the formula carried jointly with the later refinements of Whitney.

The modern viewpoint is Gian-Carlo Rota's. His 1964 paper On the foundations of combinatorial theory I ^{[Aigner 2007]} placed inclusion-exclusion inside the incidence algebra of a partially ordered set, identifying the alternating signs as the values of the Möbius function of the Boolean lattice and exhibiting inclusion-exclusion, Möbius number-theoretic inversion, and Euler-characteristic computations as instances of one inversion principle. Carlo Emilio Bonferroni's 1936 study of statistical classes ^{[Bonferroni 1936]} supplied the partial-sum inequalities that bound a union by truncated sieves, central to multiple-comparison statistics. Adriano Garsia and Stephen Milne's 1981 involution principle then closed the loop, showing that the signed cancellation underlying every sieve can be realised as an explicit weight-preserving bijection.

Bibliography Master

@book{stanley2012ec1,
  author    = {Stanley, Richard P.},
  title     = {Enumerative Combinatorics, Volume 1},
  series    = {Cambridge Studies in Advanced Mathematics},
  volume    = {49},
  edition   = {2},
  publisher = {Cambridge University Press},
  year      = {2012}
}

@book{aigner2007enumeration,
  author    = {Aigner, Martin},
  title     = {A Course in Enumeration},
  series    = {Graduate Texts in Mathematics},
  volume    = {238},
  publisher = {Springer},
  year      = {2007}
}

@article{rota1964mobius,
  author  = {Rota, Gian-Carlo},
  title   = {On the foundations of combinatorial theory I: Theory of M\"{o}bius functions},
  journal = {Zeitschrift f\"{u}r Wahrscheinlichkeitstheorie und verwandte Gebiete},
  volume  = {2},
  year    = {1964},
  pages   = {340--368}
}

@article{bonferroni1936teoria,
  author  = {Bonferroni, Carlo Emilio},
  title   = {Teoria statistica delle classi e calcolo delle probabilit\`{a}},
  journal = {Pubblicazioni del R. Istituto Superiore di Scienze Economiche e Commerciali di Firenze},
  volume  = {8},
  pages   = {3--62},
  year    = {1936}
}

@book{demoivre1718doctrine,
  author    = {de Moivre, Abraham},
  title     = {The Doctrine of Chances: or, A Method of Calculating the Probability of Events in Play},
  publisher = {W. Pearson},
  address   = {London},
  year      = {1718}
}

@article{touchard1934permutations,
  author  = {Touchard, Jacques},
  title   = {Sur un probl\`{e}me de permutations},
  journal = {Comptes Rendus de l'Acad\'{e}mie des Sciences (Paris)},
  volume  = {198},
  pages   = {631--633},
  year    = {1934}
}

@article{garsiamilne1981involution,
  author  = {Garsia, Adriano M. and Milne, Stephen C.},
  title   = {A Rogers-Ramanujan bijection},
  journal = {Journal of Combinatorial Theory, Series A},
  volume  = {31},
  number  = {3},
  pages   = {289--339},
  year    = {1981}
}

@article{valiant1979permanent,
  author  = {Valiant, Leslie G.},
  title   = {The complexity of computing the permanent},
  journal = {Theoretical Computer Science},
  volume  = {8},
  number  = {2},
  pages   = {189--201},
  year    = {1979}
}

@book{vanlintwilson2001,
  author    = {van Lint, J. H. and Wilson, R. M.},
  title     = {A Course in Combinatorics},
  edition   = {2},
  publisher = {Cambridge University Press},
  year      = {2001}
}

Prerequisites

40.01.01

Tier anchors

beginner: Stanley 2012 *Enumerative Combinatorics, Volume 1* 2e (Cambridge) §2.1 (the sieve formula by counting how often each element is counted); Brualdi 2010 *Introductory Combinatorics* 5e (Pearson) Ch. 6 for the derangement and totient examples worked by hand
intermediate: Stanley 2012 *Enumerative Combinatorics, Volume 1* 2e §2.1-2.2 (inclusion-exclusion, the complementary form, derangements, permanents and the principle of restricted positions); van Lint-Wilson 2001 *A Course in Combinatorics* 2e (Cambridge) Ch. 10 (sieve methods, the ménage problem, Bonferroni)
master: Stanley 2012 *Enumerative Combinatorics, Volume 1* 2e §2.1-2.7 and Notes (inclusion-exclusion as Möbius inversion on the Boolean lattice, the involution principle, permanents and rook polynomials, sign-reversing involutions); Aigner 2007 *A Course in Enumeration* (Springer) §5; Rota 1964 *Amer. Math. Monthly* / *Z. Wahrscheinlichkeitstheorie* 2 (the Möbius-function programme placing the sieve inside poset theory); Bonferroni 1936 *Pubbl. R. Ist. Sup. Sci. Econ. Comm. Firenze* (the partial-sum inequalities)

References

Stanley, R. P. — Enumerative Combinatorics, Volume 1 · Cambridge Studies in Advanced Mathematics 49, 2nd edition (2012). §2.1 states the principle of inclusion-exclusion in the complementary form: for properties indexed by a finite set $S$, the number of objects with none of the properties is $\sum_{T \subseteq S} (-1)^{|T|} N_{\supseteq T}$, where $N_{\supseteq T}$ counts objects having at least the properties in $T$; the union form $|A_1 \cup \cdots \cup A_n| = \sum (-1)^{|T|+1} |A_T|$ follows by complementation. §2.2 derives the derangement count $D_n = n! \sum_{k=0}^n (-1)^k/k!$, the surjection count, the Euler totient via the prime-divisor sieve, and the 'at least $m$ / exactly $m$' refinement $E_m = \sum_{k \geq m} (-1)^{k-m} \binom{k}{m} N_k$ (the Sylvester-Whitney / involution-principle formula). §2.3-2.4 develop permanents, the principle of restricted positions, and rook polynomials, with the ménage numbers as the headline application.
van Lint, J. H. & Wilson, R. M. — A Course in Combinatorics · Cambridge University Press, 2nd edition (2001), Chapter 10 ('The principle of inclusion and exclusion'). Treats the sieve formula and its complementary form, the derangement and Euler-totient applications, the Bonferroni inequalities as truncations of the alternating sum, the permanent of the board-complement matrix as the count of placements avoiding forbidden positions, and the ménage problem solved by rook polynomials on the two-diagonal board.
Aigner, M. — A Course in Enumeration · Springer Graduate Texts in Mathematics 238 (2007), §5 ('Sieve methods'). Develops inclusion-exclusion as Möbius inversion on the Boolean lattice $2^{[n]}$, the involution-principle proof of the sieve, the rook-polynomial machinery, and the asymptotic $D_n/n! \to e^{-1}$.
Bonferroni, C. E. — Teoria statistica delle classi e calcolo delle probabilità · Pubblicazioni del R. Istituto Superiore di Scienze Economiche e Commerciali di Firenze 8 (1936), 3-62. Introduces the inequalities now named after Bonferroni: truncating the inclusion-exclusion alternating sum after an even number of terms gives a lower bound, after an odd number an upper bound, for the size of a union.

Estimated time

beginner: 18m
intermediate: 45m
master: 85m