On Factorisations of Cyclic Permutations into Transpositions

Abstract

We study the factorisations of a cyclic permutation of length $n$ as a product of a minimal number of transpositions, calculating the number $f(n,m)$ of factorisations in which a fixed element is moved $m$ times. In this way, we also give a new proof-in the spirit of Clarke’s proof of Cayley’s theorem on the number of labelled trees-of the fact that there are $n^{n-2}$ such factorisations.