Building generating functions brick by brick.

摘要

This thesis introduces a method of finding and refining generating functions. By manipulating combinatorial objects known as brick tabloids, we will show how many well known generating functions may be found and subsequently generalized. New results are given as well.; The techniques described in this dissertation originate from a thorough understanding of a connection between symmetric functions and the permutation enumeration of the symmetric group. Define a homomorphism xi on the ring of symmetric functions by defining it on the elementary symmetric function en such that xi(en) = (1 - x)n-1/ n!. Brenti showed that applying xi to the homogeneous symmetric function gave a generating function for the Eulerian polynomials [Bre93, Bre90].; Beck and Remmel reproved the results of Brenti combinatorially [BR95]. A handful of authors have tinkered with their proof to discover results about the permutation enumeration for signed permutations and multiples of permutations [Bec97, Bec93, Lan01, LR, Lan02, RRW96, Wag00, Wag03]. However, the true power and adaptability of this relationship between symmetric functions and permutation enumeration will be recorded for the first time in this dissertation. We will give versatile methods unifying a large number of results in the theory of permutation enumeration for the symmetric group, subsets of the symmetric group, and assorted Coxeter groups.; Chapter 1 begins with the basic definitions of generating functions, permutation statistics, and symmetric functions needed for the journey. We give a self-contained purely combinatorial description of the ring of symmetric functions. Beck and Remmel's proofs of Brenti's results are recounted, then the chapter ends with detailed descriptions of all of the published previous uses of the techniques given in this thesis.; In Chapter 2, the factor of (1 - x) n-1in xi is changed. Each section in this chapter shows how this modification may be applied to the investigations into particular classes of permutations.; The richness of our techniques emerges in Chapter 3. Here, the factor of the form 1/n! in xi is systematically changed to provide a number of multivariate analogues for all of the results found in Chapter 2. Included in this chapter are new derivations of the exponential formula and the generating function for the Fibonacci numbers.; Each of the homomorphisms in Chapter 2 and Chapter 3 are defined on the elementary symmetric functions and applied on the homogeneous symmetric functions to give generating functions. In Chapter 4 we describe a flexible new class of symmetric functions on which to apply our homomorphisms. Modifying two parts of the homomorphism separately along with changing the symmetric function on which the homomorphisms are applied form our powerful three-pronged approach to building generating functions.; Finally, in Chapter 5, we pull the three different tools given in Chapter 2, Chapter 3, and Chapter 4 together. We will show how to take a known generating function and rebuild it using the ideas introduced in the previous chapters.