next up previous contents
Next: Introduction to graphs Up: Special Sequences of Integers Previous: Bell numbers   Contents

Inclusion-Exclusion Principle

Note that $ \lvert A\rvert = \sum_{s \in S} I_A(s)$.

Theorem 8.6.15 (Principle of Inclusion-Exclusion)   Given $ A_1, \dots, A_n \subseteq S$ then

$\displaystyle \lvert A_1 \cup \dots \cup A_n\rvert = \sum_{\emptyset \neq J \subseteq \{1,\dots,n\}}
 (-1)^{\lvert J\rvert - 1} \lvert A_J\rvert ,$   where $ A_J = \bigcap_{i \in J} A_i$.    

Proof. We consider $ \overline{A_1 \cup \dots \cup A_n}$ and note that

$\displaystyle I_{\overline{A_1 \cup \dots \cup A_n}}$ $\displaystyle = I_{\Bar{A_1} \cap \dots \cap
 \Bar{A_n}}$    
  $\displaystyle = I_{\Bar{A_1}} I_{\Bar{A_2}} \dots I_{\Bar{A_n}}$    
  $\displaystyle = (1-I_{A_1}) (1 - I_{A_2}) \dots (1 - I_{A_n})$    
  $\displaystyle = \sum_{J \subseteq \{ 1, \dots, n \}} (-1)^{\lvert J\rvert } I_{A_J},$    

Summing over $ s \in S$ we obtain the result

$\displaystyle \lvert\overline{A_1 \cup \dots \cup A_n}\rvert = \sum_{J \subseteq
 \{ 1, \dots, n \}} (-1)^{\lvert J\rvert } \lvert A_J\rvert ,$    

which is equivalent to the required result. $ \qedsymbol$

Just for the sake of it, we'll prove it again!

Proof. For each $ s \in S$ we calculate the contribution. If $ s \in S$ but $ s$ is in no $ A_i$ then there is a contribution $ 1$ to the left. The only contribution to the right is $ +1$ when $ J = \emptyset$. If $ s \in S$ and $ K = \{ i \in \{1, \dots, n \} : s \in A_i \}$ is non-empty then the contribution to the right is $ \sum_{I \subseteq K}
(-1)^{\lvert I\rvert } = \sum_{i=0}^k \binom{k}{i} (-1)^i = 0$, the same as on the left. $ \qedsymbol$

Example 8.6.16 (Euler's Phi Function)  

$\displaystyle \phi(m) = m \prod_{\substack{p \text{ prime} \\  p \mid m}} \left(1-\frac{1}{p}
 \right).$    

Proof. [Solution] Let $ m = \prod_{i=1}^n p_i^{a_i}$, where the $ p_i$ are distinct primes and $ a_i \in \mathbb{N}$. Let $ A_i$ be the set of integers less than $ m$ which are divisible by $ p_i$. Hence $ \phi(m) = \lvert\bigcap_{i=1}^n \Bar{A_i}\rvert $. Now $ \lvert A_i\rvert = \frac{m}{p_i}$, in fact for $ J \subseteq \{ 1, \dots, m \}$ we have $ \lvert A_J\rvert = \frac{m}{\prod_{i \in J} p_i}$. Thus

$\displaystyle \phi(m)$ $\displaystyle = m - \frac{m}{p_1} - \frac{m}{p_2} - \dots -
 \frac{m}{p_n}$    
  $\displaystyle + \frac{m}{p_1 p_2} + \frac{m}{p_1 p_3} + \dots + \frac{m}{p_2 p_3}
 + \dots + \frac{m}{p_{n-1} p_n}$    
  $\displaystyle \vdots$    
  $\displaystyle + (-1)^n \frac{m}{p_1 p_2 \dots p_n}$    
  $\displaystyle = m \prod_{\substack{p \text{ prime} \\ p \mid m}} \left(1-\frac{1}{p}
 \right) \qquad \text{as required.}$    

$ \qedsymbol$

Example 8.6.17 (Derangements)   Suppose we have $ n$ mathematicians at a meeting. Leaving the meeting they pick up their overcoats at random. In how many ways can this be done so that none of them has his own overcoat. This number is $ D_n$, the number of derangements of $ n$ objects.

Proof. [Solution] Let $ A_i$ be the number of ways in which mathematician number $ i$ collects his own coat. Then $ D_n = \lvert\Bar{A_1} \cap \dots \cap \Bar{A_n}\rvert $. If $ J \subseteq \{1, \dots, n \}$ with $ \lvert J\rvert = k$ then $ \lvert A_J\rvert = (n-k)!$. Thus

$\displaystyle \lvert\Bar{A_1} \cap \dots \cap \Bar{A_n}\rvert$ $\displaystyle = n! - \binom{n}{1} (n-1)!
 + \binom{n}{2} (n-2)! - \dots$    
  $\displaystyle = n! \sum_{k=0}^n \frac{(-1)^k}{k!}.$    

Thus $ D_n$ is the nearest integer to $ n!\, e^{-1}$, since $ \frac{D_n}{n!}
\to e^{-1}$ as $ n \to \infty$. $ \qedsymbol$


next up previous contents
Next: Introduction to graphs Up: Special Sequences of Integers Previous: Bell numbers   Contents
root 2002-06-10