HMMT November

Combinatorics Difficulty 5.1 AIME, harder Find the answer

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\}$ .

Your answer

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

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 $\binom{9}{5}$ ways to choose which numbers are in the cycle and 4 ! ways to create the cycle. The answer is thus $1+\binom{9}{5} \cdot 4!=3025$ .

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.