HMMT-Nov 2017 guts, Problem 28

Compute the number of functions $f:\{1,2, \ldots, 9\} \rightarrow\{1,2, \ldots, 9\}$ which satisfy $f(f(f(f(f(x)))))=$ $x$ for each $x \in\{1,2, \ldots, 9\}$.

Solution: All cycles lengths in the permutation must divide 5, which is a prime number. Either $f(x)=x$ for all $x$, or there exists exactly one permutation cycle of length 5 . In the latter case, there are $\left(\begin{array}{l}9 \\ 5\end{array}\right)$ ways to choose which numbers are in the cycle and 4 ! ways to create the cycle. The answer is thus $1+\left(\begin{array}{l}9 \\ 5\end{array}\right) \cdot 4 !=3025$. $\fbox{3025}$.

Answer: 3025