Minimal Transitive Factorizations of Permutations into Cycles

DOI10.4153/CJM-2009-052-2MaRDI QIDQ3184307zbMATH OpenOpenAlexWikidataFDO

Authors J. Irving

Publication date 14 October 2009

Published in Canadian Journal of Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

permutationscyclesbranched coveringsfactorizationsenumerative problem

Mathematics Subject Classification ID

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

Abstract: We introduce a new approach to an enumerative problem closely linked with the geometry of branched coverings; that is, we study the number of ways a permutation can be decomposed into a product of a given number of 2-cycles, 3-cycles, etc. with certain minimality and transitivity conditions imposed on the factors. The method is to encode such factorizations as planar maps with certain "descent structure" and apply a new combinatorial decomposition to make their enumeration more manageable. We apply our technique to count factorizations of permutations with one or two parts, extending earlier work of Goulden and Jackson. We also show how these methods are readily modified to count inequivalent factorizations, where equivalence is defined by permitting commutations of adjacent disjoint factors. Our technique permits a substantial generalization of recent work of Goulden, Jackson, and Latour, while allowing for a considerable simplification of their analysis.

Recommendations

• A simple recurrence for covers of the sphere with branch points of arbitrary ramification
• Inequivalent transitive factorizations into transpositions
• Minimal transitive factorizations of a permutation of type (p,q)
• Enumeration of planar constellations
• Transitive factorisations into transpositions and holomorphic mappings on the sphere

Cited in

(16)

• Parking functions, tree depth and factorizations of the full cycle into transpositions
• Inequivalent factorizations of permutations
• Expansion of polynomial Lie group integrals in terms of certain maps on surfaces, and factorizations of permutations
• Minimal factorizations of permutations into star transpositions
• Inequivalent transitive factorizations into transpositions
• Minimal transitive factorizations of a permutation of type (p,q)
• Near-central permutation factorization and Strahov's generalized Murnaghan-Nakayama rule
• Annular noncrossing permutations and minimal transitive factorizations
• Factorizations of cycles and multi-noded rooted trees
• \(k\)-factorizations of the full cycle and generalized Mahonian statistics on \(k\)-forests
• scientific article; zbMATH DE number 1766635 (Why is no real title available?)
• scientific article; zbMATH DE number 6007658 (Why is no real title available?)
• On decompositions of a cyclic permutation into a product of a given number of permutations
• Minimal factorizations of a cycle: a multivariate generating function
• Transitive factorizations of permutations and geometry
• Transitive factorizations in the symmetric group, and combinatorial aspects of singularity theory

This page was built for publication: Minimal Transitive Factorizations of Permutations into Cycles

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