DMTCS Proceedings, 20th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2008)

Font Size:  Small  Medium  Large

Minimal Factorizations of Permutations into Star Transpositions

J. Irving, A. Rattan

Abstract


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 (Reduced decompositions of permutations in terms of star transpositions, generalized catalan numbers and k-ary trees, Discrete Math. 204:329--335, 1999) in which substantial restrictions were placed on the permutation being factored.
Résumé. Nous présentons une expression compacte pour le nombre de factorisations minimales d'une permutation arbitraire de transposition de la forme (1 i). Ce résultat généralise le travail passé de Pak (Reduced decompositions of permutations in terms of star transpositions, generalized catalan numbers and k-ary trees, Discrete Math. 204:329--335, 1999) dans lequel des restrictions substantielles sont imposées sur la permutation étant factorisée.

Full Text: GZIP Compressed PostScript PostScript PDF

Valid XHTML 1.0 Transitional