User Tools

Site Tools


Bruce Sagan (Michigan State and Rutgers)

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.

seminars/comb/abstract.200603sag.txt · Last modified: 2020/01/29 14:03 (external edit)