TAOCP 3.1 Exercise 15
Suppose $f$ is a random function from a set of $m$ elements to itself, as in exercise 11.
Exercise 15. [**] [M15] If $f(x)$ is chosen at random in the sense of exercise 11, what is the probability that none of the final cycles has length 1, regardless of the choice of $X_0$?
Verified: yes
Solve time: 1m11s
Suppose $f$ is a random function from a set of $m$ elements to itself, as in exercise 11. The final cycles of $f$ are the cyclic components of the functional graph of $f$. For none of these cycles to have length 1, it is necessary and sufficient that $f(x) \neq x$ for every $x$ in the set, because a fixed point corresponds to a cycle of length 1. Each of the $m$ values $f(x)$ is chosen independently and uniformly from the $m$ elements. For a given $x$, the probability that $f(x) \neq x$ is $\frac{m-1}{m}$. Since the choices for different $x$ are independent, the probability that $f(x) \neq x$ for all $x$ is
$\left(\frac{m-1}{m}\right)^m.$
This completes the proof.
∎
$$ \boxed{\left(\frac{m-1}{m}\right)^m} $$