Sponsored by the Rutgers University Department of Mathematics and the
Center for Discrete Mathematics and Theoretical Computer Science (DIMACS)
Title: Algorithms for Permutation Statistics
Speaker: Andrew Baxter, Rutgers University
Date: Thursday, April 14, 2011 5:00pm
Location: Hill Center, Room 705, Rutgers University, Busch Campus, Piscataway, NJ
We consider the problem of counting the number of permutations containing a given number of subpermutations matching a given pattern. This "number of copies" statistic provides many interesting counting problems, including counting the number of permutations with no copies of (i.e. avoiding) a given pattern or patterns. In this thesis defense I will discuss several of these problems, providing algorithmic solutions which apply to broad classes of patterns. These include applying the Goulden-Jackson cluster method to count permutations with a given number of copies of "dashed" patterns, adapting enumeration schemes to count permutations with no copies of dashed patterns, and adapting enumeration schemes to count permutations with no copies of certain patterns and a given number of copies of others.
I will also briefly discuss the following related extensions: converting enumeration schemes into functional equations for the corresponding generating functions, pattern avoidance by even permutations, and asymptotic joint-distributions of the permutation statistics "inversion number" and "major index."
This is a Ph.D. Thesis Defense, but open to the public.