7 The Inclusion-Exclusion Principle and Applications

Theorem 7.1

The number of objects of the set \(S\) that have none of the properties \(P_1, P_2, \ldots , P_m\) is given by the alternating expression

\begin{align*} |\overline{A}_1 \cap \overline{A}_2 \cap \cdots \cap \overline{A}_m| = & |S| - \sum |A_i| + \sum |A_i \cap A_j| - \sum |A_i \cap A_j \cap A_k| + \\ & \cdots + (-1)^m |A_1 \cap A_2 \cap \cdots \cap A_m|, \tag {6.2} \end{align*}

where the first sum is over all 1-subsets \(\{ i\} \) of \(\{ 1,2,\ldots ,m\} \), the second sum is over all 2-subsets \(\{ i,j\} \) of \(\{ 1,2,\ldots ,m\} \), the third sum is over all 3-subsets \(\{ i,j,k\} \) of \(\{ 1,2,\ldots ,m\} \), and so on until the \(m\)th sum over all \(m\)-subsets of \(\{ 1,2,\ldots ,m\} \) of which the only one is itself.

Corollary 7.2

The number of objects of \(S\) which have at least one of the properties \(P_1, P_2, \ldots , P_m\) is given by

\begin{align*} |A_1 \cup A_2 \cup \cdots \cup A_m| = & \sum |A_i| - \sum |A_i \cap A_j| + \sum |A_i \cap A_j \cap A_k| - \\ & \cdots + (-1)^{m+1} |A_1 \cap A_2 \cap \cdots \cap A_m|, \tag {6.3} \end{align*}

where the summations are as specified in Theorem 6.1.1.

Theorem 7.3

For \(n \geq 1\),

\[ D_n = n! \left( 1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \cdots + (-1)^n \frac{1}{n!} \right). \]

Theorem 7.4

The number of ways to place \(n\) nonattacking, indistinguishable rooks on an \(n\)-by-\(n\) board with forbidden positions equals

\[ n! - r_1 (n-1)! + r_2 (n-2)! - \cdots + (-1)^k r_k (n-k)! + \cdots + (-1)^n r_n. \]

Theorem 7.5

For \(n \geq 1\),

\begin{align*} Q_n = \quad & n! - \binom {n-1}{1}(n-1)! + \binom {n-1}{2}(n-2)! \\ & - \binom {n-1}{3}(n-3)! + \cdots + (-1)^{n-1} \binom {n-1}{n-1}1!. \end{align*}

Theorem 7.6

Let \((X, \leq )\) be a partially ordered set with a smallest element \(0\). Let \(\mu \) be its Möbius function, and let \(F : X \to \Re \) be a real-valued function defined on \(X\). Let the function \(G : X \to \Re \) be defined by

\[ G(x) = \sum _{\{ z : z \leq x\} } F(z), \quad (x \in X). \]

Then

\[ F(x) = \sum _{\{ y : y \leq x\} } G(y) \mu (y, x), \quad (x \in X). \]

Corollary 7.7

Let \(X_n = \{ 1, 2, \ldots , n\} \) and let \(F : \mathcal{P}(X_n) \to \Re \) be a function defined on the subsets of \(X_n\). Let \(G : \mathcal{P}(X_n) \to \Re \) be the function defined by

\[ G(K) = \sum _{L \subseteq K} F(L), \quad (K \subseteq X_n). \]

Then

\[ F(K) = \sum _{L \subseteq K} (-1)^{|K| - |L|} G(L), \quad (K \subseteq X_n). \]

Theorem 7.8

Let \((X, \leq _1)\) and \((Y, \leq _2)\) be two finite partially ordered sets with Möbius functions \(\mu _1\) and \(\mu _2\), respectively. Let \(\mu \) be the Möbius function of the direct product of \((X, \leq _1)\) and \((Y, \leq _2)\). Then

\[ \mu \big((x, y), (x', y')\big) = \mu (x, x') \mu (y, y'), \quad \big((x, y), (x', y') \in X \times Y\big). \tag {6.29} \]

Theorem 7.9

Let \(F\) be a real-valued function defined on the set of positive integers. Define a real-valued function \(G\) on the positive integers by

\[ G(n) = \sum _{k : k \mid n} F(k). \]

Then, for each positive integer \(n\), we have

\[ F(n) = \sum _{k : k \mid n} \mu \left(n/k \right) G(k), \]

where we write \(\mu (n/k)\) for \(\mu (1, n/k)\).