Sponsored by the Rutgers University Department of Mathematics and the
Center for Discrete Mathematics and Theoretical Computer Science (DIMACS)
Title: Computational Methods in Permutation Patterns (Ph.D. Thesis Defense)
Speaker: Brian Nakamura, Rutgers University
Date: Thursday, March 28, 2013 5:00pm
Location: Hill Center, Room 705, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
In this thesis defense, we will discuss two variations of the classical pattern avoidance problem in permutations. The first one is on the study of consecutive patterns in permutations, where an occurrence of a pattern must occur in consecutive terms of the permutation. In this case, we develop an automated approach for deriving recurrences and functional equations that can be used for enumerating the pattern-avoiding permutations. We will also mention a Wilf-equivalence result that is a by-product of this approach.
The second case is a generalization to the classical pattern avoiding problem, where we want to enumerate permutations with exactly r occurrences of a pattern. In this case, we derive functional equations for certain families of patterns and use these to enumerate the desired permutations. We will also mention how this approach can be extended to handle multiple patterns simultaneously as well as refine by the number of inversions. Finally, we will give a brief example on how certain existing techniques can be automated so that a computer can derive rigorous results (beyond what is possible by purely human means).