Counting Patterns in Permutations and Words

The study of permutations and permutation statistics dates back hundreds of years to the time of Euler and before. In this thesis, we examine several generalizations of classical permutation statistics, most often generalizing the descent statistic, des(sigma). Chapter 1 is dedicated to providing some history and background to the work presented in later chapters. Chapter 2 reviews permutations, notations and the study of several classic permutation statistics. It is interesting to note that many surprising identities and connections to other areas of combinatorics arise as we refine the descent statistic. In Chapter 3, we consider a more refined pattern matching condition where we take into account conditions involving the equivalence classes of the elements of a descent mod k for some integer k >= 2. In general, when one includes parity conditions or conditions involving equivalence mod k, then the problem of counting the number of pattern matchings becomes more complicated. We then proceed to provide q-analogues to these findings and present them in Chapter 4. In Chapter 5, we prove some results on patterns in words. In particular we show that the generating functions for words embedding specific patterns are rational functions. In fact we also develop a method to obtain these generating functions using a finite state automaton. Thus, we can compare generating functions for words embedding different patterns. Sometimes these generating functions are the same, so many bijective questions arise from this study. We will then review some work of Jeff Remmel and Anthony Mendes. In particular, they were able to find generating functions which count occurrences of consecutive sequences in a permutation or a word which matches a given pattern by exploiting the combinatorics associated with symmetric functions. They were able to take the generating function for the number of permutations which do not contain a certain pattern and give generating functions refining permutations by both the total number of pattern matches and the number of non-overlapping pattern matches. However, as a corollary, the generating function that they produced involved a term counting the number of permutations that have consecutive overlapping patterns at certain positions. We begin to enumerate these for permutations in S4 and S5 in Chapter 6. Lastly, we look at yet another generalization of the descent statistic where we require the descent to be equal to a fixed value, k. Our results in this area are presented in Chapter 7.