====== Bruce Sagan (Michigan State and Rutgers) ======

====== Counting Permutations by Congruence Class of Major Index ======

===== Abstract for the Combinatorics Seminar 2006 March 23 =====

Let S<sub>n</sub> be the symmetric group of all permutations of {1,2,...,n}. A permutation π = a<sub>1</sub> a<sub>2</sub> ... a<sub>n</sub> in S<sub>n</sub> (written in one-line form) has major index\\
    maj π = Sum<sub>a<sub>i</sub> > a<sub>i+1</sub></sub>   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 m<sub>n</sub><sup>k,l</sup> be the k×l matrix whose (i,j) entry is the cardinality of the set\\
    {π in S<sub>n</sub> : maj π = i (mod k) and maj π<sup>-1</sup> = 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.


----