J. Irving ; A. Rattan - Minimal Factorizations of Permutations into Star Transpositions

dmtcs:3595 - Discrete Mathematics & Theoretical Computer Science, January 1, 2008, DMTCS Proceedings vol. AJ, 20th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2008) - https://doi.org/10.46298/dmtcs.3595
Minimal Factorizations of Permutations into Star TranspositionsArticle

Authors: J. Irving 1; A. Rattan 2

  • 1 Department of Mathematics and Computing Science [Halifax]
  • 2 Department of Mathematics [Cambridge]

We give a compact expression for the number of factorizations of any permutation into a minimal number of transpositions of the form $(1 i)$. Our result generalizes earlier work of Pak ($\textit{Reduced decompositions of permutations in terms of star transpositions, generalized catalan numbers and k-ary trees}$, Discrete Math. $\textbf{204}$:329―335, 1999) in which substantial restrictions were placed on the permutation being factored.


Volume: DMTCS Proceedings vol. AJ, 20th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2008)
Section: Proceedings
Published on: January 1, 2008
Imported on: May 10, 2017
Keywords: star transpositions,factorizations,permutations,symmetric group,[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]
Funding:
    Source : OpenAIRE Graph
  • Funder: Natural Sciences and Engineering Research Council of Canada

18 Documents citing this article

Consultation statistics

This page has been seen 192 times.
This article's PDF has been downloaded 204 times.