DIMACS - RUTGERS EXPERIMENTAL MATHEMATICS SEMINAR

Sponsored by the Rutgers University Department of Mathematics and the
Center for Discrete Mathematics and Theoretical Computer Science (DIMACS)

Co-organizers:

Andrew Baxter, Rutgers University, baxter{at} math [dot] rutgers [dot] edu

Doron Zeilberger, Rutgers University, zeilberg {at} math [dot] rutgers [dot] edu

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

Abstract:

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.