Enumeration of planar constellations
type: Item
instance of: scholarly article
title: Enumeration of planar constellations
zbMATH Open document ID: 0955.05004
author: Mireille Bousquet-Mélou
author: Gilles Schaeffer
published in: Advances in Applied Mathematics
publication date: 2001-02-18T00:00:00Z
review text: This paper studies transitive ordered factorizations of a given permutation. For \(n\geq 1\), let \(\sigma_0\in S_n\) be a fixed permutation with \(d_i\) cycles of length \(i\). For \(m\geq 2\), the paper counts the number of ordered \(m\)-tuples of permutations from \(S_n\) that factor \(\sigma_0\), i.e. \(\sigma_0= \sigma_1\sigma_2\cdots\sigma_m\), with the following additional properties: (1) the group generated by \(\sigma_1,\sigma_2,\dots, \sigma_m\) acts transitively on \(\{1,2,\dots, n\}\), and (2) \(\sum^m_{i=0} c(\sigma_i)= n(m- 2)+ 2\), where \(c(\sigma_i)\) denotes the number of cycles of \(\sigma_i\). The number of factorizations satisfying the conditions above is \[ m{[(m-1)n- 1]!\over [(m- 1)n- c(\sigma_0)+ 2]!} \prod_{i\geq 1} \left[i\begin{pmatrix} mi-1\\ i\end{pmatrix}\right]^{d_i}. \] A bijection relates these factorizations to some rooted planar maps. An old result of Hurwitz counting similar factorizations into transpositions yields as a specialization of this result.
Mathematics Subject Classification ID: 05A15
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 57M15
Mathematics Subject Classification ID: 05C30
zbMATH DE Number: 1501934
zbMATH Keywords: planar constellations
zbMATH Keywords: plane trees
zbMATH Keywords: Eulerian trees
zbMATH Keywords: ordered factorizations of a given permutation
zbMATH Keywords: rooted planar maps
reviewed by: László A. Székely
MaRDI profile type: Publication
OpenAlex ID: W1986886622
cites work: Enumeration of \(m\)-ary cacti
cites work: Q4071773
cites work: Q3267408
cites work: Branch Point Structure of Covering Maps Onto Nonorientable Surfaces
cites work: Q4945321
cites work: The combinatorial relationship between trees, cacti and certain connection coefficients for the symmetric group
cites work: Transitive factorisations into transpositions and holomorphic mappings on the sphere
cites work: Q3669422
cites work: Symmetric functions and Macdonald's result for top connexion coefficients in the symmetric group
cites work: Labelled trees and factorizations of a cycle into transpositions
cites work: Q5333061
cites work: Q5615284
cites work: Belyi Functions, Hypermaps and Galois Groups
cites work: Q3669450
cites work: Q4529547
cites work: Q5534009
cites work: Nonequivalent coverings of Riemann surfaces with a prescribed ramification type
cites work: A solution to a problem of Dénes: A bijection between trees and factorizations of cyclic permutations
cites work: Bijective census and random generation of Eulerian planar maps with prescribed vertex degrees
cites work: Q4003835
cites work: Minimal transitive products of transpositions---the reconstruction of a proof of A. Hurwitz
cites work: A Census of Slicings
DOI: 10.1006/AAMA.1999.0673
description: scientific article; zbMATH DE number 1501934