Counting permutations by congruence class of major index
| dc.creator | Barcelo, Helene | |
| dc.creator | Sagan, Bruce | |
| dc.creator | Sundaram, Sheila | |
| dc.date | 2005-12-30 | |
| dc.date.accessioned | 2026-07-07T06:55:54Z | |
| dc.date.available | 2026-07-07T06:55:54Z | |
| dc.description | Consider S_n, the symmetric group on n letters, and let maj pi denote the major index of a permutation pi in S_n. Given positive integers k,l and nonnegative integers i,j, define m_n^{k,l}(i,j) := number of pi in S_n such that maj pi = i (mod k) and maj pi^{-1} = j (mod l). We prove bijectively that if k,l are relatively prime and at most n then m_n^{k,l}(i,j) = n!/(kl) which, surprisingly, does not depend on i and j. Equivalently, if m_n^{k,l}(i,j) is interpreted as the (i,j)-entry of a matrix m_n^{k,l}, then this is a constant matrix under the stated conditions. This bijection is extended to show the more general result that for d at least 1 and k,l relatively prime, the matrix m_n^{kd,ld} admits a block decompostion where each block is the matrix m_n^{d,d}/(kl). We also give an explicit formula for m_n^{n,n} and show that if p is prime then m_{np}^{p,p} has a simple block decomposition. To prove these results, we use the representation theory of the symmetric group and certain restricted shuffles. | |
| dc.description | 15 pages | |
| dc.identifier | https://arxiv.org/abs/math/0512650 | |
| dc.identifier | http://arxiv.org/abs/math/0512650 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/106435 | |
| dc.subject | Combinatorics | |
| dc.subject | Number Theory | |
| dc.subject | Primary: 05A10; Secondary: 05A19, 11B50 | |
| dc.title | Counting permutations by congruence class of major index | |
| dc.type | text |