CMS/SMC
Canadian Mathematical Society
www.cms.math.ca
Canadian Mathematical Society
  location:  PublicationsjournalsCJM
Abstract view

Minimal Transitive Factorizations of Permutations into Cycles

  Published:2009-10-01
 Printed: Oct 2009
  • John Irving
Format:   HTML   LaTeX   MathJax   PDF   PostScript  

Abstract

We introduce a new approach to an enumerative problem closely linked with the geometry of branched coverings, that is, we study the number $H_{\alpha}(i_2,i_3,\dots)$ of ways a given permutation (with cycles described by the partition $\a$) can be decomposed into a product of exactly $i_2$ 2-cycles, $i_3$ 3-cycles, \emph{etc.}, with certain minimality and transitivity conditions imposed on the factors. The method is to encode such factorizations as planar maps with certain \emph{descent structure} and apply a new combinatorial decomposition to make their enumeration more manageable. We apply our technique to determine $H_{\alpha}(i_2,i_3,\dots)$ when $\a$ has one or two parts, extending earlier work of Goulden and Jackson. We also show how these methods are readily modified to count \emph{inequivalent} factorizations, where equivalence is defined by permitting commutations of adjacent disjoint factors. Our technique permits us to generalize recent work of Goulden, Jackson, and Latour, while allowing for a considerable simplification of their analysis.
MSC Classifications: 05A15, 05E10 show english descriptions Exact enumeration problems, generating functions [See also 33Cxx, 33Dxx]
Combinatorial aspects of representation theory [See also 20C30]
05A15 - Exact enumeration problems, generating functions [See also 33Cxx, 33Dxx]
05E10 - Combinatorial aspects of representation theory [See also 20C30]
 

© Canadian Mathematical Society, 2014 : https://cms.math.ca/