FUNDAMENTALNAYA
I PRIKLADNAYA MATEMATIKA
(FUNDAMENTAL AND APPLIED MATHEMATICS)
2011/2012, VOLUME 17, NUMBER 4, PAGES 25-52
A combinatorial way of counting unicellular maps and
constellations
E. A. Vassilieva
G. Schaeffer
Abstract
View as HTML
View as gif image
Our work is devoted to the bijective enumeration of the set of
factorizations of a permutation into 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.
Location: http://mech.math.msu.su/~fpm/eng/k1112/k114/k11403h.htm
Last modified: July 2, 2012