XXXV OM - III - Problem 1

Determine the number of functions $ f $ mapping an $ n $-element set to itself such that $ f^{n-1} $ is a constant function, while $ f^{n-2} $ is not a constant function, where $ f^k = f\circ f \circ \ldots \circ f $, and $ n $ is a fixed natural number greater than 2.
Suppose that $ A = \{a_1, a_2, \ldots, a_n \} $ is a given $ n $-element set, and $ f $ is a function satisfying the conditions of the problem. Consider the sets $ A, f(A), f^2(A), \ldots, f^{n-1}(A) $. From the assumption, it follows that the set $ f^{n-1}(A) $ is a singleton, while the set $ f^{n-2}(A) $ has more than one element. Furthermore, $ f^{k-1}(A) \supset f^k(A) $ for $ k = 1,2, \ldots, n - 1 $, since every element of the form $ f^k(x) $ is of the form $ f^{k-1}(y) $, where $ y = f(x) $, and $ f^{k-1}(A) \ne f^k(A) $. If $ f^{k-1}(A) = f^k(A) = \{a_{i_1}, a_{i_2}, \ldots, a_{i_r}\} $, then the function $ f $ would map the subset $ \{a_{i_1}, a_{i_2}, \ldots, a_{i_r}\} $ onto itself and would be injective on this subset. Each iteration of the function $ f $ would thus be injective on this subset, contradicting the fact that $ f^{n-1} $ is a constant function.
Therefore, the inclusions

hold, none of which is an equality. The set $ A $ has $ n $ elements, and the set $ f^{n-1}(A) $ has one element. It follows that each set in the sequence (*) has one element fewer than the previous set.
We have shown that each function $ f $ satisfying the conditions of the problem determines a sequence of subsets of $ A $, in which each subsequent subset is obtained from the previous one by discarding one element, and thus uniquely determines a permutation of the set $ A $.
On the other hand, each such sequence of subsets of $ A $ uniquely determines the function $ f $ because if

then

Functions satisfying the conditions of the problem are thus uniquely determined by permutations of the set $ A $. Their number is therefore $ n! $.