Let Sn be the symmetric group of all permutations of {1,2,...,n}. A permutation π = a1 a2 ... an in Sn (written in one-line form) has major index
maj π = Sumai > ai+1 i,
i.e., maj π is the sum of all the indices i where π has a descent.
The major index is an important statistic in combinatorics and has many
interesting properties.
Now fix two positive integers k, l which are relatively prime (i.e., have no common factors) and are at most n. Let mnk,l be the k×l matrix whose (i,j) entry is the cardinality of the set
{π in Sn : maj π = i (mod k) and maj π-1 = j (mod l)}.
Surprisingly, this matrix has all its entries equal! We will outline a
combinatorial proof of this theorem and other related results.
This is joint work with Helene Barcelo and Sheila Sundaram.