The number of prefixes of minimal factorisations of a cycle (Q311552)

Summary: 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.