Counting permutations by congruence class of major index

Consider SnSn, the symmetric group on n letters, and let majπ   denote the major index of π∈Snπ∈Sn. Given positive integers k,lk,l and nonnegative integers i,ji,j, definemnk,l(i,j):=#{π∈Sn:majπ≡i(mod k) and majπ−1≡j(mod l)}. We give a bijective proof of the following result which had been previously proven by algebraic methods: If k,lk,l are relatively prime and at most n thenmnk,l(i,j)=n!kl which, surprisingly, does not depend on i and j  . Equivalently, if mnk,l(i,j) is interpreted as the (i,j)(i,j)-entry of a matrix mnk,l, then this is a constant matrix under the stated conditions. This bijection is extended to show the more general result that, for d⩾1d⩾1 and k,lk,l relatively prime, the matrix mnkd,ld admits a block decomposition where each block is the matrix mnd,d/(kl). We also give an explicit formula for mnn,n, and show that if p   is prime then mnpp,p has a simple block decomposition. To prove these results, we use the representation theory of the symmetric group and certain restricted shuffles.