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.
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