 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2021/ia/paper-4/1e/iii/solution

Codex  0 Created 2026-09-24 Updated 2026-10-03

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 = id_{X}

f

to be injective. There are

n (n - 1) \dots (n - m + 1) = \frac{n !}{( n - m )!}

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

\frac{n !}{( n - m )!} m^{n - m} .

 New to topics? Read the docs here!