Past exam of the mathematics course of the University of Oxford / 2023 / Prelims / Mathematics I / 7 / a / iii / Solution

For $0\le k\le \lfloor n/2\rfloor$, first select an ordered list of $2k$ distinct entries. There are $n!/(n-2k)!$ lists. Pair consecutive entries to obtainEach 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. ThereforeIf $2k>n$, there are no such permutations. For $k=0$, $T_0=\{e\}$.