IMC 1998 · Problem 4

Let $A_n = \{1, 2, \dots, n\}$, where $n \ge 3$. Let $\mathcal{F}$ be the family of all non-constant functions $f : A_n \to A_n$ satisfying the following conditions:

(1) $f(k) \le f(k+1)$ for $k = 1, 2, \dots, n-1$,

(2) $f(k) = f(f(k+1))$ for $k = 1, 2, \dots, n-1$.

Find the number of functions in $\mathcal{F}$.