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 ⁽¹⁾
Monday 09/18/06	3:15 pm	A304 Wells Hall	Adam Goyt	Avoiding Partitions of a 3-element set ⁽²⁾

⁽¹⁾ Consider S_n, the symmetric group on n letters, and let majπ denote the major index of π∈ S_n. Given positive integers k,l and nonnegative integers i,j we define

m_n^k,l(i,j):=#{π∈ S_n : 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 m_n^k,l(i,j)=n!/(kl) which, surprisingly, does not depend on i and j. Equivalently, if m_n^k,l(i,j) is interpreted as the (i,j)-entry of a matrix m_n^k,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 m_n^kd,ld admits a block decompostion where each block is the matrix m_n^d,d/(kl). We also give an explicit formula for m_n^n,n and show that if p is prime then m_np^p,p has a simple block decomposition. To prove these results, we use the representation theory of the symmetric group and certain restricted shuffles.

⁽²⁾ 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.