TAOCP 1.3.3 Exercise 17
Let $C_r$ denote the number of $r$-cycles occurring among all $n!$ permutations of $n$ elements.
Section 1.3.3: Applications to Permutations
Exercise 17. [M24] (a) The text demonstrates that there are $n!H_n$ cycles altogether, among all the permutations on $n$ elements. If these cycles (including singleton cycles) are individually written on $n!H_n$ slips of paper, and if one of these slips of paper is chosen at random, what is the average length of the cycle that is thereby picked? (b) If we write the $n!$ permutations on $n!$ slips of paper, and if we choose a number $k$ at random and also choose one of the slips of paper, what is the probability that the cycle containing $k$ on that slip is an $m$-cycle? What is the average length of the cycle containing $k$?
Verified: yes
Solve time: 44s
Solution
Let $C_r$ denote the number of $r$-cycles occurring among all $n!$ permutations of $n$ elements.
Choose $r$ distinct elements and arrange them in a cycle. The number of such cycles is
$$ \binom nr (r-1)!. $$
The remaining $n-r$ elements may be permuted arbitrarily, giving $(n-r)!$ possibilities. Hence
$$ C_r=\binom nr (r-1)!(n-r)! =\frac{n!}{r}. \tag{1} $$
Therefore the total number of cycles among all permutations is
$$ \sum_{r=1}^n C_r =n!\sum_{r=1}^n\frac1r =n!H_n, $$
as stated in the text.
(a)
The slips of paper are the individual cycles themselves. The average cycle length is therefore
$$ \frac{\sum_{r=1}^n r,C_r} {\sum_{r=1}^n C_r}. $$
Using (1),
$$ \sum_{r=1}^n r,C_r = \sum_{r=1}^n r\frac{n!}{r} = \sum_{r=1}^n n! = n,n!. $$
Since the denominator is $n!H_n$,
$$ \text{average length} = \frac{n,n!}{n!H_n} = \frac{n}{H_n}. $$
Hence the answer to part (a) is
$$ \boxed{\frac{n}{H_n}}. $$
(b)
Fix an element $k$.
To determine the probability that the cycle containing $k$ is an $m$-cycle, count permutations for which this occurs.
Choose the other $m-1$ elements of the cycle:
$$ \binom{n-1}{m-1}. $$
With these $m$ elements fixed, the number of distinct cycles containing $k$ is
$$ (m-1)!. $$
Indeed, after placing $k$ first, the remaining $m-1$ elements may be arranged arbitrarily around the cycle.
The remaining $n-m$ elements may be permuted arbitrarily:
$$ (n-m)!. $$
Thus the number of permutations in which $k$ belongs to an $m$-cycle is
$$ \binom{n-1}{m-1}(m-1)!(n-m)! = (n-1)!. $$
This count is independent of $m$. Since there are $n!$ permutations altogether,
$$ \Pr{\text{$k$ lies in an $m$-cycle}} = \frac{(n-1)!}{n!} = \frac1n. $$
Therefore
$$ \boxed{\Pr{\text{$k$ lies in an $m$-cycle}}=\frac1n, \qquad 1\le m\le n.} $$
The average length of the cycle containing $k$ is
$$ \sum_{m=1}^n m\cdot \frac1n = \frac1n\sum_{m=1}^n m = \frac1n\cdot\frac{n(n+1)}2. $$
Hence
$$ \boxed{\text{average length of the cycle containing }k =\frac{n+1}{2}}. $$
This completes the proof.
∎