Past exam of the computer science course of the University of Oxford / 2021 / Artificial intelligence / 2 / f / Solution

There is exactly one solution: $X_i=i$ for $i=1,\dots ,n$. Strict increase makes all $n$ values distinct. Since all lie in the $n$-element domain $\{1,\dots ,n\}$, they must use every value, and their increasing order fixes their positions.

Equivalently, $X_i\ge i$ by propagation from the lower endpoint, and $X_i\le i$ by propagating backwards from $X_n\le n$. For general $m\ge n$, choosing any $n$-element subset determines one increasing solution, giving the binomial coefficient $\left(\genfrac{}{}{0ex}{}{m}{n}\right)$; the case $m=n$ gives $1$.