The number of prefixes of minimal factorisations of a cycle (Q311552)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The number of prefixes of minimal factorisations of a cycle |
scientific article |
Statements
The number of prefixes of minimal factorisations of a cycle (English)
0 references
13 September 2016
0 references
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.
0 references
factorisation of cycles
0 references
non-crossing partitions
0 references
parking functions
0 references
0 references
0 references