Counting permutations by congruence class of major index

Original · EN

Consider Sₙ, the symmetric group on n letters, and let maj pi denote the major index of a permutation pi in Sₙ. Given positive integers k,l and nonnegative integers i,j, define mₙᵏ,ˡ(i,j):= number of pi in Sₙ such that maj pi = i (mod k) and maj pi⁻¹ = j (mod l). We prove bijectively that if k,l are relatively prime and at most n then mₙᵏ,ˡ(i,j) = n!/(kl) which, surprisingly, does not depend on i and j. Equivalently, if mₙᵏ,ˡ(i,j) is interpreted as the (i,j)-entry of a matrix mₙᵏ,ˡ, 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ₙkd,ld admits a block decompostion where each block is the matrix mₙᵈ,ᵈ/(kl). We also give an explicit formula for mₙⁿ,ⁿ and show that if p is prime then mnpᵖ,ᵖ has a simple block decomposition. To prove these results, we use the representation theory of the symmetric group and certain restricted shuffles.