Combinatorics and Graph Theory Seminar, MSU

Date Time Location Speaker Title
Monday 09/11/06 3:00 pm A304 Wells Hall Bruce Sagan Counting permutations by congruence class of major index (1)
Monday 09/18/06 3:15 pm A304 Wells Hall Adam Goyt Avoiding Partitions of a 3-element set (2)

(1) Consider Sn, the symmetric group on n letters, and let majπ denote the major index of π∈ Sn. Given positive integers k,l and nonnegative integers i,j we define

mnk,l(i,j):=#{π∈ Sn : majπ≡ i (mod k) and majπ-1≡ j (mod l)}.
We prove bijectively that if k,l are relatively prime and at most n then
mnk,l(i,j)=n!/(kl)
which, surprisingly, does not depend on i and j. Equivalently, if mnk,l(i,j) is interpreted as the (i,j)-entry of a matrix mnk,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 mnkd,ld admits a block decompostion where each block is the matrix mnd,d/(kl). We also give an explicit formula for mnn,n and show that if p is prime then mnpp,p has a simple block decomposition. To prove these results, we use the representation theory of the symmetric group and certain restricted shuffles.

(2) Patterns in permutations have been a topic of interest since the late 1970's. In the late 1990's Klazar introduced a notion of pattern avoidance in set partitions, and considered partitions of a 4-element set. We will discuss enumerative results of partitions avoiding partitions of a 3-element set. We will also consider enumerations of partitions avoiding generalized patterns.