Last 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:

1. $$\varphi(p^k) = p^k - p^{k-1} = p^k \left(1-\frac{1}{p}\right)$$ for prime $$p$$,
2. $$\varphi$$ is multiplicative, i.e., for relatively prime numbers, $$n$$ and $$m$$, $$\varphi(n m) = \varphi(n) \varphi(m)$$.
The formula then follows from these two facts. Personally, I find it much easier to prove the function is multiplicative after finding the formula using the principle of inclusion-exclusion.