IMC 1998 · Day 2 · P10

It is clear that $id : A_n \longrightarrow A_n$, given by $id(x) = x$, does not verify condition (2). Since $id$ is the only increasing injection on $A_n$, $F$ does not contain injections. Let us take any $f \in F$ and suppose that $\#(f^{-1}(k)) \ge 2$. Since $f$ is increasing, there exists $i \in A_n$ such that $f(i) = f(i+1) = k$. In view of (2), $f(k) = f(f(i+1)) = f(i) = k$. If $\{i < k : f(i) < k\} = \emptyset$, then taking $j = \max\{i < k : f(i) < k\}$ we get $f(j) < f(j+1) = k = f(f(j+1))$, a contradiction. Hence $f(i) = k$ for $i \le k$. If $\#(f^{-1}(\{l\})) \ge 2$ for some $l \ge k$, then the similar consideration shows that $f(i) = l = k$ for $i \le k$. Hence $\#(f^{-1}\{i\}) = 0$ or 1 for every $i > k$. Therefore $f(i) \le i$ for $i > k$. If $f(l) = l$, then taking $j = \max\{i < l : f(i) < l\}$ we get $f(j) < f(j+1) = l = f(f(j+1))$, a contradiction. Thus, $f(i) \le i - 1$ for $i > k$. Let $m = \max\{i : f(i) = k\}$. Since $f$ is non-constant $m \le n-1$. Since $k = f(m) = f(f(m+1))$, $f(m+1) \in [k+1, m]$. If $f(l) > l-1$ for some $l > m+1$, then $l-1$ and $f(l)$ belong to $f^{-1}(f(l))$ and this contradicts the facts above. Hence $f(i) = i-1$ for $i > m+1$. Thus we show that every function $f$ in $F$ is defined by natural numbers $k$, $l$, $m$, where $1 \le k < l = f(m+1) \le m \le n-1$. $$f(i) = \begin{cases} k & \text{if } i \le m \\ l & \text{if } i = m+1 \\ i-1 & \text{if } i > m+1. \end{cases}$$ Then $$\#(F) = \binom{n}{3}.$$