Minimal Factorizations of Permutations into Star Transpositions
Résumé
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.
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 ($\textit{Reduced decompositions of permutations in terms of star transpositions, generalized catalan numbers and k-ary trees}$, Discrete Math. $\textbf{204}$:329―335, 1999) dans lequel des restrictions substantielles sont imposées sur la permutation étant factorisée.
Origine : Fichiers éditeurs autorisés sur une archive ouverte
Loading...