Bijections and symmetries for the factorizations of the long cycle

DOI10.1016/J.AAM.2013.01.004MaRDI QIDQ394753zbMATH OpenOpenAlexWikidataFDO

Authors Olivier Bernardi, Alejandro H. Morales

Publication date 27 January 2014

Published in Advances in Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1112.4970

zbMATH Keywords

Jackson's formulaconstellationsone-face maps

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15) Combinatorial aspects of representation theory (05E10) Combinatorial identities, bijective combinatorics (05A19)

Abstract: We study the factorizations of the permutation $(1,2,\mathrm{...},n)$ into $k$ factors of given cycle types. Using representation theory, Jackson obtained for each $k$ an elegant formula for counting these factorizations according to the number of cycles of each factor. In the cases $k=2,3$ Schaeffer and Vassilieva gave a combinatorial proof of Jackson's formula, and Morales and Vassilieva obtained more refined formulas exhibiting a surprising symmetry property. These counting results are indicative of a rich combinatorial theory which has remained elusive to this point, and it is the goal of this article to establish a series of bijections which unveil some of the combinatorial properties of the factorizations of $(1,2,\mathrm{...},n)$ into $k$ factors for all $k$. We thereby obtain refinements of Jackson's formulas which extend the cases $k=2,3$ treated by Morales and Vassilieva. Our bijections are described in terms of "constellations", which are graphs embedded in surfaces encoding the transitive factorizations of permutations.

Recommendations

• Long cycle factorizations: bijective computation in the general case
• Factorizations of large cycles in the symmetric group
• A versatile combinatorial approach of studying products of long cycles in symmetric groups
• Long cycles in \(abc\)-permutations
• A bijective proof of Jackson's formula for the number of factorizations of a cycle
• Identifying long cycles in finite alternating and symmetric groups acting on subsets
• Factorization into Symmetries and Transvections of Given Conjugacy Classes
• Cyclic Tableaux and Symmetric Functions
• Biembeddings of symmetric \(n\)-cycle systems
• Decompositions of the Kronecker product of a cycle and a path into long cycles and long paths

Cites work

• scientific article; zbMATH DE number 6909301 (Why is no real title available?)
• scientific article; zbMATH DE number 1268810 (Why is no real title available?)
• scientific article; zbMATH DE number 6928815 (Why is no real title available?)
• A bijective proof of Jackson's formula for the number of factorizations of a cycle
• A combinatorial proof of the Harer-Zagier formula
• A direct bijection for the Harer-Zagier formula
• An analogue of the Harer-Zagier formula for unicellular maps on general surfaces
• Counting trees using symmetries
• Graphs on surfaces
• Graphs on surfaces and their applications. Appendix by Don B. Zagier
• Some combinatorial problems associated with products of conjugacy classes of the symmetric group
• Some probabilistic trees with algebraic roots
• The Euler characteristic of the moduli space of curves

Cited in

(19)

• Factorization problems in complex reflection groups
• A character approach to directed genus distribution of graphs: the bipartite single-black-vertex case
• Separation probabilities for products of permutations
• \(\mathrm{GL}_n(\mathbf{F}_q)\)-analogues of factorization problems in \(\mathfrak{S}_n\)
• Factorization problems in complex reflection groups
• A simple model of trees for unicellular maps
• Some probabilistic trees with algebraic roots
• On the number of factorizations of a full cycle
• The Harer-Zagier and Jackson formulas and new results for one-face bipartite maps
• Bijective enumeration of 3-factorizations of an \(N\)-cycle
• \(\operatorname{GL}_n(\mathbb{F}_q)\)-analogues of factorization problems in the symmetric group
• Direct bijective computation of the generating series for 2 and 3-connection coefficients of the symmetric group
• Combinatorial and algebraic enumeration: a survey of the work of Ian P. Goulden and David M. Jackson
• Long cycle factorizations: bijective computation in the general case
• Factorizations of large cycles in the symmetric group
• Calculating the Euler characteristic of the moduli space of curves
• A five-element transformation monoid on labelled trees
• Cycle factorizations and 1-faced graph embeddings
• A bijective proof of Jackson's formula for the number of factorizations of a cycle

This page was built for publication: Bijections and symmetries for the factorizations of the long cycle

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q394753)