Inequivalent factorizations of permutations

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:140

Article

Berkolaik, G.¹  Irving, J.² 

[1] Texas A&M Univ, Dept Math, College Stn, TX 77843 USA

[2] St Marys Univ, Dept Math & Comp Sci, Halifax, NS B3H 3C3, Canada

关键词: Symmetric group;    Enumeration;    Permutation factorization;    Planar maps;   

DOI  :  10.1016/j.jcta.2015.12.002

来源: Elsevier

【 摘 要 】

Two factorizations of a permutation into products of cycles are equivalent if one can be obtained from the other by repeatedly interchanging adjacent disjoint factors. This paper studies the enumeration of equivalence classes under this relation. We establish general connections between inequivalent factorizations and other well-studied classes of permutation factorizations, such as monotone factorizations. We also obtain several specific enumerative results, including closed form generating series for inequivalent minimal transitive factorizations of permutations having up to three cycles. Our derivations rely on a new correspondence between inequivalent factorizations and acyclic alternating digraphs. Strong similarities between the enumerative results derived here and analogous ones for ordinary factorizations suggest that a unified theory remains to be discovered. (C) 2015 Elsevier Inc. All rights reserved.

【 授权许可】

Free