Euler, Erdős

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.