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 3element set
^{(2)}

^{(1)}
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.
^{(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 4element set. We
will
discuss enumerative results of partitions avoiding partitions of a
3element
set. We will also consider enumerations of partitions avoiding
generalized
patterns.