TAOCP 1.3.3 Exercise 25

Section 1.3.3: Applications to Permutations

Exercise 25. [M22] Prove Eq. (29).

Verified: yes
Solve time: 27m26s

Solution

Let $S_n$ be the set of all permutations of ${1,2,\dots,n}$, each taken with equal probability $1/n!$. Let $X(\pi)$ denote the number of cycles in a permutation $\pi \in S_n$. Equation (29) asserts that the mean value satisfies

$$ \mathbb{E}[X] = 1 + \frac{1}{2} + \cdots + \frac{1}{n}. $$

For $i \in {1,\dots,n}$, define $I_i(\pi)=1$ if $i$ is the smallest element in the cycle of $\pi$ containing $i$, and $I_i(\pi)=0$ otherwise. Each cycle of $\pi$ contains exactly one smallest element, since the order on ${1,\dots,n}$ is total. Hence

$$ X(\pi) = \sum_{i=1}^n I_i(\pi). $$

Taking expectations gives

$$ \mathbb{E}[X] = \sum_{i=1}^n \mathbb{E}[I_i] = \sum_{i=1}^n \mathbb{P}(I_i=1). $$

Fix $i$. Let $C_i$ denote the cycle of $\pi$ containing $i$, and let $|C_i|=k$. The event ${|C_i|=k}$ is independent of labeling inside the cycle in the sense that all choices of the remaining $k-1$ elements from ${1,\dots,n}\setminus{i}$ produce the same number of permutations.

For a fixed $k$, the number of permutations in which $|C_i|=k$ is

$$ \binom{n-1}{k-1}(k-1)!(n-k)! = (n-1)!. $$

Hence

$$ \mathbb{P}(|C_i|=k)=\frac{(n-1)!}{n!}=\frac{1}{n}. $$

Conditioned on $|C_i|=k$, the cycle $C_i$ consists of $k$ elements, and symmetry under relabeling of these $k$ elements implies that each of them is equally likely to be the smallest. Therefore

$$ \mathbb{P}(I_i=1 \mid |C_i|=k)=\frac{1}{k}. $$

Summing over all possible cycle lengths,

$$ \mathbb{P}(I_i=1)=\sum_{k=1}^n \mathbb{P}(|C_i|=k),\mathbb{P}(I_i=1 \mid |C_i|=k) = \sum_{k=1}^n \frac{1}{n}\cdot \frac{1}{k} = \frac{1}{n}\sum_{k=1}^n \frac{1}{k}. $$

Substituting into the expectation,

$$ \mathbb{E}[X] = \sum_{i=1}^n \frac{1}{n}\sum_{k=1}^n \frac{1}{k} = \sum_{k=1}^n \frac{1}{k}. $$

Thus equation (29) holds:

$$ \boxed{1 + \frac{1}{2} + \cdots + \frac{1}{n}}. $$

This completes the proof. ∎