Hostname: page-component-cd9895bd7-8ctnn Total loading time: 0 Render date: 2024-12-18T15:58:00.807Z Has data issue: false hasContentIssue false
  • English
  • Français

Minimal Transitive Factorizations of Permutations into Cycles

Published online by Cambridge University Press:  20 November 2018

John Irving
John Irving*
Affiliation:
Department of Mathematics and Computing Science, Saint Mary’s University, Halifax, NS, B3H 3C3, e-mail: [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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}},...)$ of ways a given permutation (with cycles described by the partition $\alpha $) can be decomposed into a product of exactly ${{i}_{2}}$ 2-cycles, ${{i}_{3}}$ 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 determine ${{H}_{\alpha }}({{i}_{2}},{{i}_{3}},...)$ when $\alpha $ has 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 us to generalize recent work of Goulden, Jackson, and Latour, while allowing for a considerable simplification of their analysis.

Keywords

05A1505E10
Type
Research Article
Information
Canadian Journal of Mathematics , Volume 61 , Issue 5 , 01 October 2009 , pp. 1092 - 1117
Copyright
Copyright © Canadian Mathematical Society 2009

References

[1] M., Bousquet- Mélou and Schaeffer, G., Enumeration of planar constellations. Adv. in Appl. Math. 24(2000), no. 4, 337–368.Google Scholar
[2] Eidswick, J. A., Short factorizations of permutations into transpositions. Discrete Math. 73(1989), no. 3, 293–243.Google Scholar
[3] Ekedahl, T., Lando, S., Shapiro, M., and Vainshtein, A., On Hurwitz numbers and Hodge integrals. C. R. Acad. Sci. Paris Sér. I Math. 328(1999), no. 12, 1175–1180.Google Scholar
[4] Goryunov, V. and Lando, S., On enumeration of meromorphic functions on the line . In: The Arnoldfest. Fields Inst. Commun. 24, American Mathematical Society, Providence, RI, 1999, pp. 209–223.Google Scholar
[5] Goulden, I. P. and Jackson, D. M., Combinatorial Enumeration. Wiley Interscience, New York, 1983.Google Scholar
[6] Goulden, I. P. and Jackson, D. M., The combinatorial relationship between trees, cacti and certain connection coefficients for the symmetric group. European J. Combin. 13(1992), no. 5, 357–365.Google Scholar
[7] Goulden, I. P. and Jackson, D. M., Symmetric functions and Macdonald's result for top connexion coefficients in the symmetric group. J. Algebra 166(1994), no. 2, 364–378.Google Scholar
[8] Goulden, I. P. and Jackson, D. M., Transitive factorisations into transpositions and holomorphic mappings on the sphere. Proc. Amer. Math. Soc. 125(1997), no. 1, 51–60.Google Scholar
[9] Goulden, I. P. and Jackson, D. M., Transitive factorizations in the symmetric group, and combinatorial aspects of singularity theory. Europ. J. Combinatorics 21(2000), no. 8, 1001–1016.Google Scholar
[10] Goulden, I. P., Jackson, D. M., and Latour, F. G., Inequivalent transitive factorizations into transpositions. Canad. J. Math 53(2001), no. 4, 758–779.Google Scholar
[11] Goulden, I. P., Jackson, D. M., and Vakil, R., The Gromov-Witten potential of a point, Hurwitz numbers, and Hodge integrals , Proc. London Math. Soc. 83(2001), no. 3, 563–581.Google Scholar
[12] Goulden, I. P., Jackson, D. M., and Vakil, R., Towards the geometry of double Hurwitz numbers. Adv. Math. 198(2005), no. 1, 43–92.Google Scholar
[13] Hurwitz, A., Über Riemann’sche Flächen mit gegebenen Verzweigungspunkten. Math. Ann. 39(1891), no. 1, 1–60.Google Scholar
[14] Irving, J. C., Combinatorial Constructions for Transitive Factorizations in the Symmetric Group. Ph.D. thesis, University of Waterloo, 2004.Google Scholar
[15] Longyear, J. Q., A peculiar partition identity. Discrete Math. 78(1989), no. 1-2, 115–118.Google Scholar
[16] Moszkowski, P., A solution to a problem of Dénes: a bijection between trees and factorizations of cyclic permutations. European J. Combin. 10(1989), no. 1, 13–16.Google Scholar
[17] Springer, C. M., Factorizations, trees, and cacti, Eighth International Conference on Formal Power Series and Algebraic Combinatorics, University of Minnesota, June 25–29, 1996, pp. 427–438.Google Scholar