Geodesic
A combinatorial way of counting unicellular maps and constellations
Fundamentalʹnaâ i prikladnaâ matematika, Tome 17 (2012) no. 4, pp. 25-52
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

Our work is devoted to the bijective enumeration of the set of factorizations of a permutation into $m$ factors with a given number of cycles. Previously, this major problem in combinatorics and its various specializations were mainly considered from character theoretic or algebraic geometry point of view. Let us specially mention here the works of Harer and Zagier or Kontsevich. In 1988, Jackson reported a very general formula solving this problem. However, to the author's own admission this result left little room for combinatorial interpretation and no bijective proof of it was known yet. In 2001, Lass found a combinatorial proof of the celebrated special case of Jackson's formula known as Harer–Zagier formula. This work was followed by Goulden and Nica, who presented in 2004 another combinatorial proof involving a direct bijection. In the past two years, we have introduced new sets of objects called partitioned maps and partitioned cacti, the enumeration of which allowed us to construct bijective proofs for more general cases of Jackson's formula. 
@article{FPM_2012_17_4_a2,
     author = {E. A. Vassilieva and G. Schaeffer},
     title = {A~combinatorial way of counting unicellular maps and constellations},
     journal = {Fundamentalʹna\^a i prikladna\^a matematika},
     pages = {25--52},
     year = {2012},
     volume = {17},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/FPM_2012_17_4_a2/}
}
TY  - JOUR
AU  - E. A. Vassilieva
AU  - G. Schaeffer
TI  - A combinatorial way of counting unicellular maps and constellations
JO  - Fundamentalʹnaâ i prikladnaâ matematika
PY  - 2012
SP  - 25
EP  - 52
VL  - 17
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/FPM_2012_17_4_a2/
LA  - ru
ID  - FPM_2012_17_4_a2
ER  - 
%0 Journal Article
%A E. A. Vassilieva
%A G. Schaeffer
%T A combinatorial way of counting unicellular maps and constellations
%J Fundamentalʹnaâ i prikladnaâ matematika
%D 2012
%P 25-52
%V 17
%N 4
%U http://geodesic.mathdoc.fr/item/FPM_2012_17_4_a2/
%G ru
%F FPM_2012_17_4_a2
E. A. Vassilieva; G. Schaeffer. A combinatorial way of counting unicellular maps and constellations. Fundamentalʹnaâ i prikladnaâ matematika, Tome 17 (2012) no. 4, pp. 25-52. http://geodesic.mathdoc.fr/item/FPM_2012_17_4_a2/

[1] Adrianov N. M., “An analogue of the Harer–Zagier formula for unicellular two-color maps”, Funct. Anal. Appl., 31:3 (1997), 149–155 | DOI | MR | Zbl

[2] Cori R., Machi A., “Maps, hypermaps and their automorphisms: a survey. I”, Exposition. Math., 10 (1992), 403–427 | MR | Zbl

[3] Goulden I. P., Jackson D. M., Combinatorial Enumeration, Wiley, New York, 1983 | MR | Zbl

[4] Goulden I. P., Nica A., “A direct bijection for the Harer–Zagier formula”, J. Combin. Theory Ser. A, 111 (2005), 224–238 | DOI | MR | Zbl

[5] Goupil A., Schaeffer G., “Factoring $n$-cycles and counting maps of given genus”, European. J. Combin., 19:7 (1998), 819–834 | DOI | MR | Zbl

[6] Harer J., Zagier D., “The Euler characteristic of the moduli space of curves”, Invent. Math., 85 (1986), 457–486 | DOI | MR

[7] Jackson D. M., “Some combinatorial problems associated with products of conjugacy classes of the symmetric group”, J. Combin. Theory Ser. A, 49 (1988), 363–369 | DOI | MR | Zbl

[8] Kontsevich M., “Intersection theory on the moduli space of curves and the matrix Airy function”, Comm. Math. Phys., 147 (1992), 1–23 | DOI | MR | Zbl

[9] Lass B., “Démonstration combinatoire de la formule de Harer–Zagier”, C. R. Acad. Sci. Paris Sér. I, 333 (2001), 155–160 | DOI | MR | Zbl

[10] Schaeffer G., Vassilieva E., “A bijective proof of Jackson's formula for the number of factorizations of a cycle”, J. Combin. Theory Ser. A, 115:6 (2008), 903–924 | DOI | MR | Zbl

[11] Schaeffer G., Vassilieva E., “Partitioned cacti: a bijective approach to the cycle factorization problem”, Proc. of FPSAC' 08

[12] Stanton D., White D., Constructive Combinatorics, Springer, New York, 1986 | MR | Zbl