 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-oxford/2023/prelims/mathematics-i/7/a/iii/solution

For

0 \leq k \leq ⌊ n /2 ⌋

, first select an ordered list of

2 k

distinct entries. There are

n! / (n - 2 k)!

lists. Pair consecutive entries to obtain

(a_{1} a_{2}) (a_{3} a_{4}) \dots (a_{2 k - 1} a_{2 k}) .

Each product of

k

disjoint transpositions is counted

2^{k} k!

times: each pair has two orientations, and the

k

pairs can be ordered in

k!

ways. There is no other duplication, by uniqueness of the disjoint cycle decomposition. Therefore

∣ T_{k} ∣ = \frac{n !}{2 ^{k} k ! ( n - 2 k )!} .

2 k > n

, there are no such permutations. For

k = 0

T_{0} = {e}

 New to topics? Read the docs here!