= Solution
This can fail in the same example as in part (i): $g\circ f$ is injective on the singleton $X$, but $g(a)=g(b)$.
For the final count, $g\circ f=\operatorname{id}_X$ forces $f$ to be injective. There are
$$
n(n-1)\cdots(n-m+1)=\frac{n!}{(n-m)!}
$$
such <function>[functions] $f$. Once $f$ is chosen, $g$ is forced on the $m$ elements of $f(X)$ and has $m$ independent choices at each of the other $n-m$ elements of $Y$. Hence the number of pairs is
$$
\boxed{\frac{n!}{(n-m)!}m^{n-m}.}
$$
Back to article page
