Enumeration of Planar Constellations

✍ Scribed by Mireille Bousquet-Mélou; Gilles Schaeffer

• Publisher: Elsevier Science
• Year: 2000
• Tongue: English
• Weight: 270 KB
• Volume: 24
• Category: Article
• ISSN: 0196-8858
• DOI: 10.1006/aama.1999.0673

✦ Synopsis

The enumeration of transitive ordered factorizations of a given permutation is a combinatorial problem related to singularity theory. Let n ≥ 1, and let σ 0 be a permutation of n having d i cycles of length i, for i ≥ 1. Let m ≥ 2. We prove that the number of m-tuples σ 1 σ m of permutations of n such that

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 and extends the method previously applied to Eulerian maps by the second author. Our result might remind the reader of an old theorem of Hurwitz, giving the number of mtuples of 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.