### Sidebar

seminars:comb:abstract.200603sag

# Counting Permutations by Congruence Class of Major Index

## Abstract for the Combinatorics Seminar 2006 March 23

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 π = Suma<sub>i > ai+1</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 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.