Enumeration of planar constellations

The enumeration of transitive ordered factorizations of a given permutation is a combinatorial problem related to singularity theory. Let n greater th an or equal to 1, and let sigma(0) be a permutation of C-n having d(i) cycl es of length i, for i greater than or equal to 1. Let m greater than or equ al to 2. We prove that the number of m-tuples (sigma(1),..., sigma(m)) of p ermutations of C-n such that sigma(1)sigma(2)...sigma(m) = sigma(0), the group generated by sigma(1),..., sigma(m) acts transitively on {1, 2,.. ., n}, Sigma(i=0)(m) c(sigma(i)) = n(m-1) + 2, where c(sigma(i)) denotes the numbe r of cycles of sigma(i), is [GRAPHICS] A one-to-one correspondence relates these m-tuples to some rooted planar ma ps, which we call constellations and enumerate via a bijection with some bi colored trees. For m = 2, we recover a formula of Tutte for the number of E ulerian 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 Hunw itz, giving the number of m-tuples of transpositions satisfying the above c onditions. Indeed, we show that our result implies Hurwitz' theorem. We als o briefly discuss its implications for the enumeration of nonequivalent cov erings of the sphere. (C) 2000 Academic Press