The inclusion–exclusion principle

Theorem

The inclusion–exclusion principle

T-029Home MU-105Threads structure · number

Statement

Let \( n \in \mathbb{N} \) with \( n \ge 1 \), and let \( A_1, A_2, \dots, A_n \) be finite sets (subsets of some common set, so that unions and intersections are defined). Write \( [n] = \{1, 2, \dots, n\} \). Then \[ \left| \bigcup_{i=1}^{n} A_i \right| \;=\; \sum_{\emptyset \neq S \subseteq [n]} (-1)^{|S|+1} \left| \bigcap_{i \in S} A_i \right| \;=\; \sum_{i=1}^{n} |A_i| \;-\; \sum_{1 \le i \lt j \le n} |A_i \cap A_j| \;+\; \sum_{1 \le i \lt j \lt k \le n} |A_i \cap A_j \cap A_k| \;-\; \cdots \;+\; (-1)^{n+1} \, |A_1 \cap \cdots \cap A_n| . \] The sum runs over all \( 2^n - 1 \) non-empty index sets \( S \subseteq [n] \); the hypotheses are that \( n \) is finite and each \( A_i \) is finite, so that every cardinality appearing is a natural number and the alternating sum is a well-defined integer.

Why it matters

Counting a union directly is hard because elements belonging to several of the sets are counted several times; inclusion–exclusion is the exact, systematic correction. It converts a question about a union — typically "how many objects have at least one of these properties?" — into questions about intersections, which are usually far easier: "how many objects have this specific list of properties simultaneously?" Almost every classical enumeration formula — derangements, surjection counts, Euler's totient \( \varphi \), the sieve of Eratosthenes–Legendre — is a single application of this theorem.

Beyond exact counting, the theorem is the entry point to sieve theory in number theory and to Möbius inversion in algebraic combinatorics: inclusion–exclusion is precisely Möbius inversion over the Boolean lattice of subsets of \( [n] \). Its truncations (the Bonferroni inequalities) power probabilistic estimates throughout statistics and combinatorics.

Hypotheses

Hypothesis.Each \( A_i \) is finite. Take \( A_1 = A_2 = \mathbb{N} \). The formula would read \( |\mathbb{N} \cup \mathbb{N}| = |\mathbb{N}| + |\mathbb{N}| - |\mathbb{N} \cap \mathbb{N}| \), i.e. \( \infty = \infty + \infty - \infty \): the subtraction of infinite cardinalities is undefined, and no consistent value can be assigned. (Cardinal arithmetic has no subtraction: \( \aleph_0 - \aleph_0 \) is ill-posed.)

Hypothesis.The family is finite (\( n \in \mathbb{N} \)). With infinitely many sets, even all finite — say \( A_i = \{1\} \) for every \( i \in \mathbb{N} \) — the right-hand side becomes a "sum" over infinitely many index sets \( S \) whose terms do not tend to \( 0 \) and whose value depends on the order of summation; the alternating series is divergent, while the left-hand side is \( 1 \).

Hypothesis."Size" means cardinality — more generally, any finitely additive set function. The proof uses only that \( |A| = \sum_{x} \mathbf{1}_A(x) \), i.e. finite additivity over disjoint pieces; the identity therefore holds verbatim for any finite measure \( \mu \) (Poincaré's formula in probability). It fails for non-additive set functions: with \( f(A) = |A|^2 \) and disjoint singletons \( A, B \), the left side is \( f(A \cup B) = 4 \) but the right side is \( 1 + 1 - 0 = 2 \).

Proof

Let \( U = A_1 \cup \cdots \cup A_n \); this is a finite set, being a finite union of finite sets. For \( A \subseteq U \) let \( \mathbf{1}_A : U \to \{0,1\} \) denote the indicator function, \( \mathbf{1}_A(x) = 1 \) if \( x \in A \) and \( 0 \) otherwise.

\[ |A| \;=\; \sum_{x \in U} \mathbf{1}_A(x) \qquad \text{for every } A \subseteq U. \]

Definition of cardinality via indicators: each element of \( A \) contributes exactly \( 1 \) and each element of \( U \setminus A \) contributes \( 0 \); the sum is finite because \( U \) is finite. A

\[ \mathbf{1}_{\,\bigcup_{i=1}^{n} A_i}(x) \;=\; 1 \;-\; \prod_{i=1}^{n} \bigl( 1 - \mathbf{1}_{A_i}(x) \bigr) \qquad \text{for every } x \in U. \]

Key idea — verify pointwise by cases. If \( x \notin A_i \) for all \( i \), every factor is \( 1 - 0 = 1 \), the product is \( 1 \), and both sides equal \( 0 \). If \( x \in A_{i_0} \) for some \( i_0 \), the factor \( 1 - \mathbf{1}_{A_{i_0}}(x) = 0 \) annihilates the product, and both sides equal \( 1 \). These two cases are exhaustive. B

\[ \prod_{i=1}^{n} (1 - t_i) \;=\; \sum_{S \subseteq [n]} (-1)^{|S|} \prod_{i \in S} t_i \qquad \text{in } \mathbb{Z}[t_1, \dots, t_n], \]

Generalised distributive law, proved by induction on \( n \). Base \( n = 0 \): both sides are \( 1 \) (empty product convention \( \prod_{i \in \emptyset} t_i = 1 \)). Inductive step: \( \prod_{i=1}^{n+1}(1 - t_i) = \bigl( \sum_{S \subseteq [n]} (-1)^{|S|} \prod_{i \in S} t_i \bigr) (1 - t_{n+1}) \); expanding, the subsets of \( [n+1] \) not containing \( n+1 \) come from the first summand and those containing \( n+1 \) from the second, with the sign \( (-1)^{|S|+1} = (-1)^{|S \cup \{n+1\}|} \) as required. Every \( S \subseteq [n+1] \) arises exactly once. C

\[ \prod_{i \in S} \mathbf{1}_{A_i}(x) \;=\; \mathbf{1}_{\,\bigcap_{i \in S} A_i}(x) \qquad \text{for every non-empty } S \subseteq [n],\; x \in U. \]

Both sides are \( 1 \) exactly when \( x \in A_i \) for every \( i \in S \), i.e. \( x \in \bigcap_{i \in S} A_i \) — the definition of intersection; a product of values in \( \{0,1\} \) equals \( 1 \) iff every factor is \( 1 \). A

\[ \mathbf{1}_{\,\bigcup_{i=1}^{n} A_i}(x) \;=\; 1 - \sum_{S \subseteq [n]} (-1)^{|S|} \, \mathbf{1}_{\,\bigcap_{i \in S} A_i}(x) \;=\; \sum_{\emptyset \neq S \subseteq [n]} (-1)^{|S|+1} \, \mathbf{1}_{\,\bigcap_{i \in S} A_i}(x). \]

Substitute Step 3 with \( t_i = \mathbf{1}_{A_i}(x) \) into Step 2, then rewrite each monomial via Step 4. The term \( S = \emptyset \) contributes \( (-1)^{0} \cdot 1 = 1 \) (empty product), which cancels the leading \( 1 \); moving the remaining terms across the minus sign flips \( (-1)^{|S|} \) to \( (-1)^{|S|+1} \). A

\[ \sum_{x \in U} \; \sum_{\emptyset \neq S \subseteq [n]} (-1)^{|S|+1} \, \mathbf{1}_{\,\bigcap_{i \in S} A_i}(x) \;=\; \sum_{\emptyset \neq S \subseteq [n]} (-1)^{|S|+1} \sum_{x \in U} \mathbf{1}_{\,\bigcap_{i \in S} A_i}(x). \]

Interchange of two finite sums: both index sets ( \( U \), and the \( 2^n - 1 \) non-empty subsets of \( [n] \) ) are finite, so the double sum is a finite sum of integers and may be reordered freely by commutativity and associativity of addition in \( \mathbb{Z} \). No convergence issue arises — this is the point at which finiteness of both \( U \) and \( n \) is essential. C

\[ \left| \bigcup_{i=1}^{n} A_i \right| \;=\; \sum_{x \in U} \mathbf{1}_{\,\bigcup_i A_i}(x) \;=\; \sum_{\emptyset \neq S \subseteq [n]} (-1)^{|S|+1} \left| \bigcap_{i \in S} A_i \right| . \]

Apply Step 1 to the left side, substitute the pointwise identity of Step 5 under the sum, interchange by Step 6, and apply Step 1 again to each inner sum \( \sum_{x \in U} \mathbf{1}_{\cap_{i \in S} A_i}(x) = \left| \bigcap_{i \in S} A_i \right| \) (each intersection is a subset of \( U \)). This is the theorem. A

Consistency check (the "per-element" reading): an element lying in exactly \( k \ge 1 \) of the sets is counted \( \sum_{j=1}^{k} (-1)^{j+1} \binom{k}{j} = 1 - (1-1)^{k} = 1 \) time by the right-hand side.

Not needed for the proof above, but it is the classical double-counting argument in miniature: the element contributes to \( \binom{k}{j} \) of the \( j \)-fold intersections, and the binomial theorem \( (1-1)^k = \sum_{j=0}^{k} \binom{k}{j} (-1)^j = 0 \) for \( k \ge 1 \) shows the net count is exactly \( 1 \). This recovers Step 5 elementwise. B

Result

\[ \left| \bigcup_{i=1}^{n} A_i \right| \;=\; \sum_{\emptyset \neq S \subseteq [n]} (-1)^{|S|+1} \left| \bigcap_{i \in S} A_i \right| \qquad ( n \in \mathbb{N},\; A_1, \dots, A_n \text{ finite} ) \]

Reading. To count how many objects lie in at least one of the sets: add the single-set sizes, subtract every pairwise overlap (those were counted twice), add back every triple overlap (those were subtracted once too often), and continue alternating up to the full \( n \)-fold intersection. Each element ends up counted exactly once, no matter how many of the sets it belongs to.

Scope. Any finite family of finite sets — no disjointness, distinctness, or structure assumptions whatever; the sets may repeat or nest arbitrarily. The identical proof gives the version for any finitely additive measure \( \mu \) on an algebra of sets with all \( \mu(A_i) \) finite (in particular probabilities: Poincaré's formula \( \mathbb{P}(\bigcup A_i) = \sum (-1)^{|S|+1} \mathbb{P}(\bigcap_{i \in S} A_i) \)). It does not extend to infinitely many sets, to infinite cardinalities, or to non-additive set functions.

Corollaries & converses

Two and three sets. \( |A \cup B| = |A| + |B| - |A \cap B| \), and \( |A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C| \) — the cases \( n = 2, 3 \).
Complement (sieve) form. If all \( A_i \subseteq U \) with \( U \) finite, then \( \bigl| U \setminus \bigcup_i A_i \bigr| = \sum_{S \subseteq [n]} (-1)^{|S|} \bigl| \bigcap_{i \in S} A_i \bigr| \), where the \( S = \emptyset \) term is \( |U| \). This is the form used in most applications ("none of the properties").
Bonferroni inequalities. Truncating the sum after all terms with \( |S| \le m \) overshoots for \( m \) odd and undershoots for \( m \) even: the partial sums alternately bound \( \bigl| \bigcup_i A_i \bigr| \) above and below. (Proof: the per-element count \( \sum_{j=0}^{m} (-1)^{j+1} \binom{k}{j} \) alternates around \( 1 \) because partial sums of alternating binomial coefficients have the sign of the last term kept.)
Derangements. The number of permutations of \( [n] \) with no fixed point is \( D_n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!} \) — apply the sieve form with \( A_i = \{\sigma : \sigma(i) = i\} \).
Surjections. The number of surjections from an \( m \)-set onto a \( k \)-set is \( \sum_{j=0}^{k} (-1)^j \binom{k}{j} (k-j)^m \).
Euler's totient. \( \varphi(n) = n \prod_{p \mid n} \bigl( 1 - \frac{1}{p} \bigr) \) — sieve the multiples of each prime divisor out of \( [n] \) (Problem 5 below).
Converse fails. The intersection cardinalities determine \( \bigl| \bigcup_i A_i \bigr| \), but not conversely: knowing \( |A \cup B| = 2 \) is consistent with \( |A| = |B| = 1, A \cap B = \emptyset \) and with \( |A| = 2, B = A \). The map from intersection data to union size is many-to-one and loses all structural information.

Fails without

Infinite sets. \( A = 2\mathbb{Z} \), \( B = 3\mathbb{Z} \) (even and treble integers). All of \( |A|, |B|, |A \cap B| = |6\mathbb{Z}| \) and \( |A \cup B| \) are countably infinite; the "identity" \( \aleph_0 = \aleph_0 + \aleph_0 - \aleph_0 \) is meaningless because cardinal subtraction is undefined — one can "assign" any value from \( 0 \) to \( \aleph_0 \) to the right-hand side by regrouping. The theorem genuinely needs each cardinality to be a natural number.
Infinitely many sets. \( A_i = \{1\} \) for all \( i \in \mathbb{N} \). The left side is \( 1 \). On the right, every finite non-empty \( S \) gives \( \bigl| \bigcap_{i \in S} A_i \bigr| = 1 \), so the "sum" is \( \sum_S (-1)^{|S|+1} \) over infinitely many \( S \) — a series whose terms do not tend to zero and whose partial sums depend on enumeration order. No value can be consistently assigned.
Dropping the higher-order corrections. \( A = B = C = \{1\} \). Stopping after the pairwise terms: \( 1 + 1 + 1 - 1 - 1 - 1 = 0 \neq 1 = |A \cup B \cup C| \); the triple term \( +1 \) is not optional. (This is the Bonferroni undershoot at even truncation depth, realised exactly.)
Non-additive "size". With \( f(A) = |A|^2 \), \( A = \{1\} \), \( B = \{2\} \): \( f(A \cup B) = 4 \) but \( f(A) + f(B) - f(A \cap B) = 1 + 1 - 0 = 2 \). Finite additivity of the set function is what the proof's Step 1 encodes, and it cannot be dropped.

Common errors

Sign drift. Writing \( (-1)^{|S|} \) where \( (-1)^{|S|+1} \) is needed (or vice versa). Mnemonic: in the union form the single-set terms come with \( + \); in the complement/sieve form the sign is \( (-1)^{|S|} \) because the \( S = \emptyset \) term \( |U| \) is positive. Confusing the two forms is the single most common error.
Stopping early. Computing \( \sum |A_i| - \sum |A_i \cap A_j| \) for three or more sets and calling it the answer. That is a Bonferroni lower bound, not the count; the example \( A = B = C = \{1\} \) above gives \( 0 \) instead of \( 1 \).
"At least one" versus "exactly one". The theorem counts elements in at least one set. The number in exactly one set is a different alternating sum ( \( \sum |A_i| - 2 \sum |A_i \cap A_j| + 3 \sum |A_i \cap A_j \cap A_k| - \cdots \) ); substituting one for the other silently is a frequent exam error.
Floor-function slips in divisibility counts. When \( A_d = \{ m \le N : d \mid m \} \), \( |A_d| = \lfloor N/d \rfloor \), and \( |A_c \cap A_d| = \lfloor N / \operatorname{lcm}(c,d) \rfloor \) — not \( \lfloor N/(cd) \rfloor \) unless \( \gcd(c,d) = 1 \). Using the product instead of the lcm for non-coprime moduli gives wrong counts.
Assuming symmetry that is not there. The compact formula \( \sum_k (-1)^{k+1} \binom{n}{k} N_k \) is valid only when all \( k \)-fold intersections have the same size \( N_k \) (as for derangements). Applying it when the intersections vary in size is unjustified.

Discussion

The two-set case \( |A \cup B| = |A| + |B| - |A \cap B| \) is ancient common sense; the general principle crystallised in the nineteenth century. It is often attributed jointly to Daniel da Silva (1854) and J. J. Sylvester (1883), and the formula is sometimes called the da Silva–Sylvester formula; but the method is older in specific guises — Nicolas Bernoulli and Pierre Rémond de Montmort used exactly this alternating sieve around 1708–1713 to count derangements (the "problème des rencontres"), and Legendre's 1808 count of primes below \( x \) via sieving multiples of small primes is inclusion–exclusion applied to number theory. In probability the identity for \( \mathbb{P}(\bigcup A_i) \) carries Poincaré's name.

Structurally, the theorem is a statement about the algebra of indicator functions: Step 2's identity \( \mathbf{1}_{\cup A_i} = 1 - \prod (1 - \mathbf{1}_{A_i}) \) is De Morgan's law rendered multiplicatively, and the whole proof is the observation that cardinality is the linear functional \( f \mapsto \sum_x f(x) \) applied to a polynomial identity. This viewpoint explains at once why the theorem holds for arbitrary finitely additive measures, and why truncations behave so well: the Bonferroni inequalities are inherited from inequalities between partial sums of \( (1-1)^k \).

The principle is also the simplest sieve, and its limitation is instructive: with \( n \) sets the exact formula has \( 2^n - 1 \) terms, which is computationally hopeless for large \( n \) and analytically wasteful when the intersections are only known approximately, since the error terms accumulate across exponentially many summands. Modern sieve theory (Brun's pure sieve of 1915 onward, then Selberg's) exists precisely to replace the exact alternating sum with truncated or weighted versions whose error can be controlled — Brun's proof that the sum of reciprocals of twin primes converges is, at heart, a quantitatively disciplined inclusion–exclusion.

The definitive generalisation is Rota's theory of Möbius functions on partially ordered sets (1964). For a finite poset \( P \), Möbius inversion states that \( g(x) = \sum_{y \le x} f(y) \) for all \( x \) if and only if \( f(x) = \sum_{y \le x} \mu(y, x) \, g(y) \), where \( \mu \) is the Möbius function of \( P \). Inclusion–exclusion is the special case \( P = \) the Boolean lattice \( 2^{[n]} \), whose Möbius function is \( \mu(S, T) = (-1)^{|T| - |S|} \) for \( S \subseteq T \); the classical Möbius function of number theory arises the same way from the divisibility lattice, which is why Euler's totient computation (Problem 5) and the sieve form of the theorem look identical in shape. In this light the alternating signs are not a combinatorial accident but the values of a canonical inverse in the incidence algebra of \( 2^{[n]} \).

Common misconceptions. The theorem does not require the sets to be distinct, non-empty, or in "general position" — it is an unconditional identity. It does not say the union is large or small; it is exact, not an estimate (its truncations are the estimates). And it does not compute "exactly one" or "exactly \( m \)" memberships directly — those need the related but distinct formula of Problem 4's per-element method with different coefficients.

Worked examples

Example 1 (divisibility count). How many integers in \( \{1, 2, \dots, 1000\} \) are divisible by at least one of \( 2, 3, 5 \)?

Set \( A_d = \{ m \in [1000] : d \mid m \} \) for \( d = 2, 3, 5 \); the answer is \( |A_2 \cup A_3 \cup A_5| \), and \( |A_d| = \lfloor 1000/d \rfloor \).

Modelling step: "divisible by at least one" is exactly membership in the union; the multiples of \( d \) in \( [N] \) number \( \lfloor N/d \rfloor \). A

\[ |A_2| = 500, \quad |A_3| = 333, \quad |A_5| = 200. \]

Direct evaluation: \( \lfloor 1000/2 \rfloor = 500 \), \( \lfloor 1000/3 \rfloor = 333 \), \( \lfloor 1000/5 \rfloor = 200 \). A

An integer lies in \( A_c \cap A_d \) iff it is divisible by \( \operatorname{lcm}(c,d) \); here the moduli are pairwise coprime, so the lcm is the product. B

\[ |A_2 \cap A_3 \cap A_5| = \lfloor 1000/30 \rfloor = 33. \]

Same reasoning with \( \operatorname{lcm}(2,3,5) = 30 \). A

\[ |A_2 \cup A_3 \cup A_5| = (500 + 333 + 200) - (166 + 100 + 66) + 33 = 1033 - 332 + 33 = 734. \]

Inclusion–exclusion for \( n = 3 \), with every term computed in Steps 2–4. A

\[ \#\{ m \le 1000 : 2 \mid m \text{ or } 3 \mid m \text{ or } 5 \mid m \} = 734 \]

Reading. Nearly three-quarters of the first thousand integers have a prime factor below \( 7 \); equivalently \( 266 \) of them are coprime to \( 30 \), close to the density prediction \( 1000 \cdot \frac{1}{2} \cdot \frac{2}{3} \cdot \frac{4}{5} \approx 266.7 \).

Scope. The method works for any \( N \) and any finite set of moduli, provided intersections use lcms.

Example 2 (derangements of four letters). Four letters are placed into four addressed envelopes at random, one per envelope. In how many of the \( 4! = 24 \) arrangements does no letter reach its own envelope?

Let \( A_i = \{ \sigma \in S_4 : \sigma(i) = i \} \) for \( i = 1, \dots, 4 \): the arrangements in which letter \( i \) is correctly placed. The answer is \( 4! - |A_1 \cup A_2 \cup A_3 \cup A_4| \).

Modelling: "no letter correct" is the complement of "at least one correct", i.e. of the union; \( |S_4| = 24 \). A

\[ \left| \bigcap_{i \in S} A_i \right| = (4 - |S|)! \qquad \text{for every non-empty } S \subseteq [4]. \]

Key computation: fixing \( \sigma(i) = i \) for all \( i \in S \) leaves a free permutation of the remaining \( 4 - |S| \) letters, and there are \( (4 - |S|)! \) of those. The intersection size depends only on \( |S| \) — the symmetric situation. B

\[ |A_1 \cup A_2 \cup A_3 \cup A_4| = \sum_{k=1}^{4} (-1)^{k+1} \binom{4}{k} (4-k)! = \binom{4}{1} 3! - \binom{4}{2} 2! + \binom{4}{3} 1! - \binom{4}{4} 0! \]

Inclusion–exclusion, grouping the \( \binom{4}{k} \) index sets \( S \) of each size \( k \), legal because Step 2 shows all intersections of a given size are equal. A

\[ |A_1 \cup A_2 \cup A_3 \cup A_4| = 4 \cdot 6 - 6 \cdot 2 + 4 \cdot 1 - 1 \cdot 1 = 24 - 12 + 4 - 1 = 15. \]

Arithmetic. A

\[ D_4 = 24 - 15 = 9 = 4! \left( 1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \frac{1}{4!} \right). \]

Complement count; the rewritten form is the general derangement formula \( D_n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!} \), verified here: \( 24 (1 - 1 + \frac12 - \frac16 + \frac{1}{24}) = 24 - 24 + 12 - 4 + 1 = 9 \). B

\[ D_4 = 9 \]

Reading. Nine of the twenty-four arrangements misplace every letter — a proportion \( 9/24 = 0.375 \), already close to the limiting value \( e^{-1} \approx 0.3679 \).

Scope. The identical computation for general \( n \) gives \( D_n = n! \sum_{k=0}^{n} (-1)^k / k! \), the nearest integer to \( n!/e \) for \( n \ge 1 \).

Problems

In a class of 60 students, 30 study algebra, 25 study analysis, and 12 study both. How many study at least one of the two, and how many study neither?
Solution
With \( A \) the algebraists and \( B \) the analysts, inclusion–exclusion for two sets gives \( |A \cup B| = |A| + |B| - |A \cap B| = 30 + 25 - 12 = 43 \). Hence \( 43 \) students study at least one subject, and \( 60 - 43 = 17 \) study neither. (The subtraction of \( 12 \) corrects for the double-count of students in both sets: they were counted once in the \( 30 \) and once in the \( 25 \).)
How many integers in \( \{1, \dots, 1000\} \) are divisible by none of \( 2, 3, 5 \)? Compare with the heuristic \( 1000 \bigl( 1 - \frac12 \bigr) \bigl( 1 - \frac13 \bigr) \bigl( 1 - \frac15 \bigr) \).
Solution
By Worked Example 1, \( |A_2 \cup A_3 \cup A_5| = 734 \), so the count divisible by none is \( 1000 - 734 = 266 \). The heuristic (treating divisibility by \( 2, 3, 5 \) as independent events of probabilities \( \frac12, \frac13, \frac15 \)) predicts \( 1000 \cdot \frac12 \cdot \frac23 \cdot \frac45 = \frac{4000}{15} = 266.\overline{6} \). The exact answer \( 266 \) differs only because of the floor functions; for \( N \) a multiple of \( 30 \) the two agree exactly, since then every \( \lfloor N/d \rfloor = N/d \) and the sieve sum factorises as \( N \prod_p (1 - \frac1p) \).
Count the surjections from a \( 5 \)-element set onto a \( 3 \)-element set.
Solution
Let the codomain be \( \{1,2,3\} \) and let \( A_j \) be the set of functions from the \( 5 \)-set to \( \{1,2,3\} \) that miss the value \( j \). A function is a surjection iff it lies in none of the \( A_j \), so the count is \( 3^5 - |A_1 \cup A_2 \cup A_3| \). For \( S \subseteq [3] \), \( \bigl| \bigcap_{j \in S} A_j \bigr| = (3 - |S|)^5 \), since such functions map into the \( 3 - |S| \) remaining values. By the sieve form,
\[ \#\text{surjections} = \sum_{k=0}^{3} (-1)^k \binom{3}{k} (3-k)^5 = 243 - 3 \cdot 32 + 3 \cdot 1 - 0 = 150. \]
Check: \( 150 = 3! \cdot S(5,3) \) where \( S(5,3) = 25 \) is a Stirling number of the second kind, as it must be (choose the partition into \( 3 \) blocks, then bijectively label the blocks).
Prove the first two Bonferroni inequalities: for finite sets \( A_1, \dots, A_n \), \[ \sum_{i=1}^{n} |A_i| - \sum_{1 \le i \lt j \le n} |A_i \cap A_j| \;\le\; \left| \bigcup_{i=1}^{n} A_i \right| \;\le\; \sum_{i=1}^{n} |A_i|. \]
Solution
Fix \( x \in \bigcup_i A_i \) and let \( k \ge 1 \) be the number of indices \( i \) with \( x \in A_i \). Count the contribution of \( x \) to each expression. To \( \bigl| \bigcup_i A_i \bigr| \): exactly \( 1 \). To \( \sum_i |A_i| \): exactly \( k \). To \( \sum_{i \lt j} |A_i \cap A_j| \): exactly \( \binom{k}{2} \), one for each pair of sets containing \( x \). Elements outside the union contribute \( 0 \) everywhere. Summing over elements, the two inequalities reduce to the pointwise claims
\[ k - \binom{k}{2} \;\le\; 1 \;\le\; k \qquad \text{for every integer } k \ge 1. \]
The right inequality is immediate. For the left: \( k - \binom{k}{2} = k - \frac{k(k-1)}{2} = \frac{k(3-k)}{2} \), which equals \( 1 \) at \( k = 1, 2 \) and is \( \le 0 \) for \( k \ge 3 \); in all cases it is \( \le 1 \). Summing the pointwise inequalities over the finitely many \( x \) (legal since all sums are finite) gives both bounds. Note both bounds are tight: equality on the right holds iff the \( A_i \) are pairwise disjoint ( \( k = 1 \) always), and on the left iff no element lies in more than two of the sets.
Let \( n \ge 2 \) have distinct prime divisors \( p_1, \dots, p_r \). Using inclusion–exclusion, prove Euler's formula \[ \varphi(n) = n \prod_{j=1}^{r} \left( 1 - \frac{1}{p_j} \right), \] where \( \varphi(n) = \#\{ 1 \le m \le n : \gcd(m, n) = 1 \} \).
Solution
Let \( A_j = \{ 1 \le m \le n : p_j \mid m \} \). Then \( \gcd(m, n) \gt 1 \) iff some prime divides both \( m \) and \( n \), iff \( m \in \bigcup_j A_j \); hence \( \varphi(n) = n - \bigl| \bigcup_{j=1}^{r} A_j \bigr| \). For \( S \subseteq [r] \) put \( d_S = \prod_{j \in S} p_j \); since distinct primes are coprime, \( \bigcap_{j \in S} A_j \) is the set of multiples of \( d_S \) in \( [n] \), and because \( d_S \mid n \) exactly \( n / d_S \) such multiples exist (no floor needed — this is where \( p_j \mid n \) is used). The sieve form of inclusion–exclusion gives
\[ \varphi(n) = \sum_{S \subseteq [r]} (-1)^{|S|} \frac{n}{d_S} = n \sum_{S \subseteq [r]} (-1)^{|S|} \prod_{j \in S} \frac{1}{p_j} = n \prod_{j=1}^{r} \left( 1 - \frac{1}{p_j} \right), \]
where the last equality is the generalised distributive law of Proof Step 3 with \( t_j = 1/p_j \). For example \( \varphi(30) = 30 \cdot \frac12 \cdot \frac23 \cdot \frac45 = 8 \), matching the direct count \( \{1, 7, 11, 13, 17, 19, 23, 29\} \).