Counting permutations by congruence class of major index

Details Counting permutations by congruence class of major index Counting permutations by congruence class of major index

2005-12-30

arxiv.org/abs/math/0512650v1

Mathematics

Combinatorics

15 pages

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Counting permutations by congruence class of major index does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Counting permutations by congruence class of major index, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Counting permutations by congruence class of major index will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-507741