Past exam of the mathematics course of the University of Cambridge / 2021 / ia / Paper 4 / 1E / iii / 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={\mathrm{id}}_X$ forces $f$ to be injective. There aresuch 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