Algorithms for Permutation Statistics
Ph.D. Dissertation, Rutgers University
Abstract: Two sequences u, v of n positive integers are order isomorphic if ui < uj if and only if
vi < j for all pairs (i, j). A permutation p is said to contain q as a pattern if some
subsequence of p is order isomorphic to q. The subsequence a copy of q. This notion of pattern containment
is generalized to include adjacency restrictions.
The primary permutation statistics studied in this work are written in terms of the number of copies of a
given pattern or patterns. The central concern of this thesis is to compute answers to problems of the
following type: Given patterns q(1), ..., q(t) and nonnegative numbers
k1, ..., kt how many permutations of length n have ki copies of q(i)
for each i?" The techniques which apply will depend on the nature of the patterns (i), as well as whether or not all
ki = 0.
Chapter Summaries:
- Chapter 1: Introduction.
Provides a overview of the problems and history related to pattern avoidance and permutation statistics. - Chapter 2: The Cluster Method and Dashed Patterns.
A recurrence to count the number of multiset permutations with k copies of a dashed pattern of the form x-yz. This is a rewrite of the material originally appearing in Applying the cluster method to count occurrences of generalized permutation patterns. - Chapter 3: Enumeration Schemes and Dashed Patterns
Zeilberger's and Vatter's enumeration schemes are shown to be effective for counting permutations avoiding dashed patterns as well. This chapter is a precursor to the article Enumeration Schemes for Dashed Patterns. [Joint work with Lara Pudwell.] - Chapter 4: Enumeration Schemes and Permutation Statistics
We show how to use enumeration schemes to count the number of permutations which avoid a set of forbidden patterns and have a given number of inversions. This material previously appeared as Refining enumeration schemes to count according to inversion number. This chapter also shows how to use enumeration schemes to count pattern-avoiding permutations with a given number of copies of a given consecutive pattern. The relevant material for this second refinment will appear in Refining enumeration schemes to count according to consecutive patterns. - Chapter 5: The Umbral Transfer Matrix Method and Enumeration Schemes
We show through several examples how one can use enumeration schemes to inform the construction of a system of functional equations for the relevant generating functions. This chapter is a precursor to the article Translating enumeration schemes into functional equations. - Chapter 6: Pattern Avoidance and Sign
We define and investigate the notion of even-Wilf-equivalence. This chapter is a precursor to the article Some results on even-Wilf-equivalence. [Joint work with Aaron Jaggard.] - Chapter 7: Asymptotic Independence of Inversion Number and Major Index
We investigate the asymptotic joint-distribution of the inversion number and major index over permutations of length n as n approaches infinity. This is a rewrite of the material originally appearing in The number of inversions and the major index of permutations are asymptotically joint-independently normal. [Joint work with Doron Zeilberger.]