A~combinatorial way of counting unicellular maps and constellations

E. A. Vassilieva ; G. Schaeffer

Fundamentalʹnaâ i prikladnaâ matematika, Tome 17 (2012) no. 4, pp. 25-52

Résumé

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.