Inclusion-Exclusion Principle (Pt. 2)
By Jean Pierre MutanguhaLast post was a proof for the Inclusion-Exclusion Principle and now this post is a couple of examples using it. The first example will revisit derangements (first mentioned in Power of Generating Functions); the second is the formula for Euler's phi function. Yes, many posts will end up mentioning Euler one way or another.
Definition 1. A derangement is a permutation on a set \(S\) with no fixed point. \(D(n)\) denotes the number of derangements on a set with \(n\) elements.
Theorem 2. \[ D(n) = n!\sum_{i=0}^n \frac{(-1)^i}{i!} \]
Last time, I claimed this theorem has an almost trivial proof using the Inclusion-Exclusion Principle:
Proof: Let \(U\) be the set of all permutations of length \(n\) and \(S_i\) be the set of permutations all length \(n\) that fix the \(i-th\) element. So:
\[ \begin{aligned} D(n) &= |U| - \sum |S_i| + \sum |S_i \cap S_j| - \sum |S_i \cap S_j \cap S_k| + \cdots + (-1)^n |S_1 \cap \cdots \cap S_n| \\ &= n! - \binom{n}{1} (n-1)! + \binom{n}{2} (n-2)! - \binom{n}{3} (n-3)! + \cdots + (-1)^n \binom{n}{n} (n-n)! \\ &= n! - \frac{n!}{1!} + \frac{n!}{2!} - \frac{n!}{3!} + \cdots + (-1)^n \frac{n!}{n!} \\ &= n!\sum_{i=0}^n \frac{(-1)^i}{i!} \end{aligned} \]
\(\Box\)
For the next example, I will skip defining \(U\) and \(S_i\) and use the principle implicitly. It should be obvious how to define the relevant sets.
Definition 3. Euler's totient function, \(\varphi(n)\), is the number of positive integers less than \(n\) that are relatively prime to \(n\).
Theorem 4. Let \(P=\{ p_i : p_i \text{ is prime and } p_i | n\}\), then \[\varphi(n) = n \prod_{p \in P} \left(1 - \frac{1}{p}\right)\]
Proof: \[ \begin{aligned} \varphi(n) &= n - \sum \frac{n}{p_i} + \sum \frac{n}{p_i p_j} -\sum \frac{n}{p_i p_j p_k} + \cdots + (-1)^{|P|} \frac{n}{p_1 p_2 \cdots p} \\ &= n \left(1 - \sum \frac{1}{p_i} + \sum \frac{1}{p_i p_j} -\sum \frac{1}{p_i p_j p_k} + \cdots + (-1)^{|P|} \frac{1}{p_1 p_2 \cdots p } \right) \\ &= n \prod_{p \in P} \left(1-\frac{1}{p}\right) \end{aligned} \]
\(\Box\)
The last step uses the following identity: \[ \begin{aligned} \prod_{i=1}^n (1 - x_i) &= 1 - \sum x_i + \sum x_i x_j - \sum x_i x_j x_k + \cdots + (-1)^n x_1 x_2 \cdots x_n \\ & = \sum_{I \subset \{1, 2, \ldots, n\}} (-1)^{|I|}\prod_{i \in I} x_i \end{aligned} \] I like this proof because it is short and straight-forward unlike the one in my number-theory book. The latter proof shows:
- \(\varphi(p^k) = p^k - p^{k-1} = p^k \left(1-\frac{1}{p}\right)\) for prime \(p\),
- \(\varphi\) is multiplicative, i.e., for relatively prime numbers, \(n\) and \(m\), \(\varphi(n m) = \varphi(n) \varphi(m)\).