On counting permutations by pairs of congruence classes of major index

Hélène Barcelo ; Robert Maule ; Sheila Sundaram

The electronic journal of combinatorics, Tome 9 (2002)

Résumé

For a fixed positive integer $n,$ let $S_n$ denote the symmetric group of $n!$ permutations on $n$ symbols, and let maj${(\sigma)}$ denote the major index of a permutation $\sigma.$ Fix positive integers $k < \ell\leq n,$ and nonnegative integers $i,j.$ Let $m_n(i\backslash k; j\backslash \ell)$ denote the cardinality of the set $\{\sigma\in S_n:$ maj$(\sigma)\equiv i \pmod k,$ maj$ (\sigma^{-1})\equiv j \pmod \ell\}.$ In this paper we use combinatorial methods to investigate these numbers. Results of Gordon and Roselle imply that when $k,$ $\ell$ are relatively prime, $$ m_n(i\backslash k; j\backslash \ell)= { {n!}\over{k\cdot\ell}} .$$ We give a combinatorial proof of this in the case when $\ell$ divides $n-1$ and $k$ divides $n.$

Détail

DOI : 10.37236/1638

Classification : 05A15, 05A05
Mots-clés : major index of a permutation