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 Transpositions
Authors: J. Irving 1; A. Rattan 2
NULL##NULL
J. Irving;A. Rattan
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.