Geodesic
The number of prefixes of minimal factorisations of a cycle
Thierry Lévy1
1Universite Pierre et Marie Curie
The electronic journal of combinatorics, Tome 23 (2016) no. 3
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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.
DOI : 10.37236/4799
Classification : 05C38, 05C70, 05C25, 05A18
Mots-clés : factorisation of cycles, non-crossing partitions, parking functions

Thierry Lévy  1

1 Universite Pierre et Marie Curie 
@article{10_37236_4799,
     author = {Thierry L\'evy},
     title = {The number of prefixes of minimal factorisations of a cycle},
     journal = {The electronic journal of combinatorics},
     year = {2016},
     volume = {23},
     number = {3},
     doi = {10.37236/4799},
     zbl = {1344.05079},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/4799/}
}
TY  - JOUR
AU  - Thierry Lévy
TI  - The number of prefixes of minimal factorisations of a cycle
JO  - The electronic journal of combinatorics
PY  - 2016
VL  - 23
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.37236/4799/
DO  - 10.37236/4799
ID  - 10_37236_4799
ER  - 
%0 Journal Article
%A Thierry Lévy
%T The number of prefixes of minimal factorisations of a cycle
%J The electronic journal of combinatorics
%D 2016
%V 23
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/4799/
%R 10.37236/4799
%F 10_37236_4799
Thierry Lévy. The number of prefixes of minimal factorisations of a cycle. The electronic journal of combinatorics, Tome 23 (2016) no. 3. doi: 10.37236/4799

Cité par Sources :