2005/12/30 by Hélène Barcelo, Helene Barcelo, Bruce Sagan +5
Engineering · Mathematics · #11B50 #Advanced Combinatorial Mathematics #Advanced Mathematical Identities #Artificial intelligence #Class (philosophy) #Combinatorics #Combinatorics (math.CO) #Computer science #Congruence (geometry) #FOS: Mathematics #Geometry #Index (typography) #Mathematics #Number Theory (math.NT) #Primary: 05A10 #Secondary: 05A19 #Statistics #graph theory and CDMA systems #math.CO #math.NT #msc:05A10 #msc:05A19 #msc:11B50
paper · pdf · doi:10.48550/arxiv.math/0512650
15 pages
arxiv created 2005/12/30 · openalex publication_date 2005/12/30 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
Consider Sn, the symmetric group on n letters, and let maj pi denote the major index of a permutation pi in Sn. Given positive integers k,l and nonnegative integers i,j, define mnk,l(i,j) := number of pi in Sn 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 mnk,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)-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 at least 1 and k,l relatively prime, the matrix mnkd,ld admits a block decompostion 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.