The Number of Prefixes of Minimal Factorisations of a Cycle

Abstract

We prove in two different ways that the number of distinct prefixes of length $k$ of minimal factorisations of the $n$-cycle $(1\ldots n)$ as a product of $n-1$ transpositions is $\binom{n}{k+1}n^{k-1}$. Our first proof is not bijective but makes use of a correspondence between minimal factorisations and Cayley trees. The second proof consists of establishing a bijection between the set which we want to enumerate and the set of parking functions of a certain kind, which can be counted by a standard conjugation argument.