2013 Putnam B5

Let $X = \{1, 2, \dots, n\}$, and let $k \in X$. Show that there are exactly $k \cdot n^{n-1}$ functions $f: X \to X$ such that for every $x \in X$ there is a $j \geq 0$ such that $f^{(j)}(x) \leq k$.

[Here $f^{(j)}$ denotes the $j$\textsuperscript{th} iterate of $f$, so that $f^{(0)}(x) = x$ and $f^{(j+1)}(x) = f(f^{(j)}(x))$.]

设 $X = \{1, 2, \dots, n\}$，并设 $k \in X$。证明正好存在 $k \cdot n^{n-1}$ 函数 $f: X \to X$，使得对于每个 $x \in X$ 都有一个 $j \geq 0$ 使得 $f^{(j)}(x) \leq k$。

[此处 $f^{(j)}$ 表示 $f$ 的第 $j$\textsuperscript{th} 次迭代，因此 $f^{(0)}(x) = x$ 且 $f^{(j+1)}(x) = f(f^{(j)}(x))$。]