Bijections and symmetries for the factorizations of the long cycle

DOI10.1016/J.AAM.2013.01.004zbMATH Open1280.05006arXiv1112.4970OpenAlexW1987001941WikidataQ114214533 ScholiaQ114214533MaRDI QIDQ394753FDOQ394753

Authors: Olivier Bernardi, Alejandro H. Morales 

Publication date: 27 January 2014

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

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.

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

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

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)

Cites Work

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

Cited In (19)

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

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)