Putnam 2013, Problem B-5

Let $X = \{1,2,\ldots,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^{\text{th}}$ iterate of $f$, so that $f^{(0)}(x) = x$ and $f^{(j+1)}(x) = f(f^{(j)}(x))$.]

Solution:
**First solution:** We assume $n \geq 1$ unless otherwise specified. For $T$ a set and $S_1, S_2$ two subsets of $T$, we say that a function $f: T \to T$ iterates $S_1$ into $S_2$ if for each $x \in S_1$, there is a $j \geq 0$ such that $f^{(j)}(x) \in S_2$.

**Lemma 1.** Fix $k \in X$. Let $f, g: X \to X$ be two functions such that $f$ iterates $X$ into $\{1, \ldots, k\}$ and $f(x) = g(x)$ for $x \in \{k+1, \ldots, n\}$. Then $g$ also iterates $X$ into $\{1, \ldots, k\}$.

*Proof.* For $x \in X$, by hypothesis there exists a nonnegative integer $j$ such that $f^{(j)}(x) \in \{1, \ldots, k\}$. Choose the integer $j$ as small as possible; then $f^{(i)}(x) \in \{k+1, \ldots, n\}$ for $0 \leq i < j$. By induction on $i$, we have $f^{(i)}(x) = g^{(i)}(x)$ for $i = 0, \ldots, j$, so in particular $g^{(j)}(x) \in \{1, \ldots, k\}$. This proves the claim. $\square$

We proceed by induction on $n-k$, the case $n-k = 0$ being trivial. For the induction step, we need only confirm that the number $x$ of functions $f: X \to X$ which iterate $X$ into $\{1, \ldots, k+1\}$ but not into $\{1, \ldots, k\}$ is equal to $n^{n-1}$. These are precisely the functions for which there is a unique cycle $C$ containing only numbers in $\{k+1, \ldots, n\}$ and said cycle contains $k+1$. Suppose $C$ has length $\ell \in \{1, \ldots, n-k\}$. For a fixed choice of $\ell$, we may choose the underlying set of $C$ in $\binom{n-k-1}{\ell-1}$ ways and the cycle structure in $(\ell-1)!$ ways. Given $C$, the functions $f$ we want are the ones that act on $C$ as specified and iterate $X$ into $\{1, \ldots, k\} \cup C$. By Lemma 1, the number of such functions is $n^{-\ell}$ times the total number of functions that iterate $X$ into $\{1, \ldots, k\} \cup C$. By the induction hypothesis, we compute the number of functions which iterate $X$ into $\{1, \ldots, k+1\}$ but not into $\{1, \ldots, k\}$ to be

$$\sum_{\ell=1}^{n-k} (n-k-1) \cdots (n-k-\ell+1)(k+\ell)n^{n-\ell-1}$$

By rewriting this as a telescoping sum, we get

$$\sum_{\ell=1}^{n-k} (n-k-1) \cdots (n-k-\ell+1)(n)n^{n-\ell-1}$$
$$- \sum_{\ell=1}^{n-k} (n-k-1) \cdots (n-k-\ell+1)(n-k-\ell)n^{n-\ell-1}$$
$$= \sum_{\ell=0}^{n-k-1} (n-k-1) \cdots (n-k-\ell)n^{n-\ell-1}$$
$$- \sum_{\ell=1}^{n-k} (n-k-1) \cdots (n-k-\ell)n^{n-\ell-1}$$
$$= n^{n-1}.$$

as desired.

**Second solution:** For $T$ a set, $f: T \to T$ a function, and $S$ a subset of $T$, we define the contraction of $f$ at $S$ as the function $g: \{*\} \cup (T-S) \to \{*\} \cup (T-S)$ given by

$$g(x) = \begin{cases} 
* & x = * \\
* & x \neq *, f(x) \in S \\
f(x) & x \neq *, f(x) \notin S.
\end{cases}$$

**Lemma 2.** For $S \subseteq X$ of cardinality $\ell \geq 0$, there are $\ell n^{n-\ell-1}$ functions $f: \{*\} \cup X \to \{*\} \cup X$ with $f^{-1}(*) = \{*\} \cup S$ which iterate $X$ into $\{*\}$.

*Proof.* We induct on $n$. If $\ell = n$ then there is nothing to check. Otherwise, put $T = f^{-1}(S)$, which must be nonempty. The contraction $g$ of $f$ at $\{*\} \cup S$ is then a function on $\{*\} \cup (X-S)$ with $f^{-1}(*) = \{*\} \cup T$ which iterates $X-S$ into $\{*\}$. Moreover, for given $T$, each such $g$ arises from $\ell^{|T|}$ functions of the desired form. Summing over $T$ and invoking the induction hypothesis, we see that the number of functions $f$ is

$$\sum_{k=1}^{n-\ell} \binom{n-\ell}{k} \ell^k \cdot k(n-\ell)^{n-\ell-k-1}$$
$$= \sum_{k=1}^{n-\ell} \binom{n-\ell-1}{k-1} \ell^k (n-\ell)^{n-\ell-k} = \ell n^{n-\ell-1}$$

as claimed. $\square$

We now count functions $f: X \to X$ which iterate $X$ into $\{1, \ldots, k\}$. By Lemma 1 of the first solution, this count equals $n^k$ times the number of functions with $f(1) = \cdots = f(k) = 1$ which iterate $X$ into $\{1, \ldots, k\}$. For such a function $f$, put $S = \{k+1, \ldots, n\} \cap f^{-1}(\{1, \ldots, k\})$ and let $g$ be the contraction of $f$ at $\{1, \ldots, k\}$; then $g^{-1}(*) = * \cup \{S\}$ and $g$ iterates