TAOCP 3.1 Exercise 14
Let $C(f)$ denote the number of distinct final cycles of a mapping $f$ on an $m$-element set $M=\{1,\ldots,m\}$.
Exercise 14. [**] [M38] If $f(x)$ is chosen at random in the sense of exercise 11, what is the average number of distinct final cycles obtainable by varying the starting value? [See exercise 8(b).]
Verified: yes
Solve time: 2m55s
Let $C(f)$ denote the number of distinct final cycles of a mapping $f$ on an $m$-element set $M={1,\ldots,m}$. Since every connected component of a functional digraph contains exactly one directed cycle, $C(f)$ is also the number of connected components of the mapping graph.
We compute the expectation of $C(f)$ when $f$ is chosen uniformly from the $m^m$ mappings of $M$ into itself.
For each $k\ge1$, let $X_k$ be the number of cycles of length $k$. Then
$$ C(f)=\sum_{k=1}^{m} X_k. $$
Hence, by linearity of expectation,
$$ E[C]=\sum_{k=1}^{m} E[X_k]. $$
It remains to determine $E[X_k]$.
Consider a fixed $k$-element subset $S\subseteq M$. The number of directed $k$-cycles on $S$ is
$$ (k-1)!, $$
since there are $k!$ cyclic orderings and each cycle is counted $k$ times by rotation.
For a particular such cycle, the probability that all $k$ prescribed edges occur in a random mapping is
$$ \left(\frac1m\right)^k, $$
because the values $f(x)$ for distinct $x$ are chosen independently and uniformly.
Therefore the expected number of $k$-cycles is
$$ E[X_k] = \binom{m}{k}(k-1)! \left(\frac1m\right)^k. $$
Simplifying,
$$ E[X_k] = \frac{m!}{(m-k)!}\frac1{k,m^k}. $$
Summing over all possible cycle lengths,
$$ E[C] = \sum_{k=1}^{m} \frac{m!}{(m-k)!}\frac1{k,m^k}. $$
Thus the average number of distinct final cycles obtainable by varying the starting value is
$$ \boxed{ \sum_{k=1}^{m} \frac{m!}{(m-k)!m^k},\frac1k }. $$
This agrees with the enumeration of cycles in Exercise 8(b).
For large $m$, using the approximation
$$ \frac{m!}{(m-k)!m^k} = \prod_{j=0}^{k-1}\left(1-\frac{j}{m}\right), $$
one obtains the well-known asymptotic estimate
$$ E[C] = \frac12\log m +\frac12(\gamma+\log 2) +o(1), $$
where $\gamma$ is Euler's constant.
$\square$