Enumeration of planar constellations

Mireille Bousquet-Melou Gilles Schaeffer 1
1 POLKA - Polynomials, Combinatorics, Arithmetic
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : The enumeration of transitive ordered factorizations of a given permutation is a combinatorial problem related to singularity theory. Let $n\ge 1$, $m \ge 2$, and let $\si_0$ be a permutation of $\Sn_n$ having $d_i$ cycles of length $i$, for $i \ge 1$. We prove that the number of $m$-tuples $(\si_1, \ldots ,\si_m)$ of permutatinos of $\Sn_n$ such that: - $\si_1 \si_2 \cdots \si_m = \si_0$, - the group generated by $\si_1 , \ldots , \si_m$ acts transitively on $\{1, 2, \ldots , n\}$, - $\sum_{i=0}^m c(\si_i) = n(m-1)+2$, where $c(\si_i)$ denotes the number of cycles of $\si_i$, is $$m \ \frac{[(m-1)n-1]!}{[(m-1)n-c(\si_0)+2]!}\ \prod_{i \ge 1} \left[ i {mi-1 \choose i} \right] ^{d_i}.$$ A one-to-one correspondence relates these $m$-tuples to some rooted planar maps, which we call constellations and enumerate via a bijection with some bicolored trees. For $m=2$, we recover a formula of Tutte for the number of Eulerian maps. The proof relies on the idea that maps are conjugacy classes of trees. Our result might remind the reader of an old theorem of Hurwitz, giving the number of $m$-tuples of {\em transpositions\/} satisfying the above conditions. Indeed, we show that our result implies Hurwitz' theorem. We also briefly discuss its implications for the enumeration of nonequivalent coverings of the sphere.
Type de document :
Article dans une revue
Advances in Applied Mathematics, Elsevier, 2000, 24 (4), pp.337-368
Liste complète des métadonnées

Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 08:53:17
Dernière modification le : jeudi 11 janvier 2018 - 06:19:48


  • HAL Id : inria-00099358, version 1



Mireille Bousquet-Melou, Gilles Schaeffer. Enumeration of planar constellations. Advances in Applied Mathematics, Elsevier, 2000, 24 (4), pp.337-368. 〈inria-00099358〉



Consultations de la notice