Enumeration of Set Partitions Refined by Crossing and Nesting Numbers

Author: 
Date created: 
2014-12-02
Identifier: 
etd8774
Keywords: 
Set partitions
Crossings and nestings
Automata
Generating functions
Enumeration
Abstract: 

The standard representation of set partitions gives rise to two natural statistics: a crossing number and a nesting number. Chen, Deng, Du, Stanley, and Yan (2007) proved, via a non-trivial bijection involving sequences of Young tableaux that these statistics have a symmetric joint distribution. Recent results by Marberg (2013) has lead to algorithmic tools for the enumeration of set partitions with fixed crossing number and fixed nesting number. In this thesis we further consider set partitions refined by these two statistics. These sub-classes can be recognized by finite automata, and consequently have rational generating functions. Our main contribution is an investigation into the structure of the automata, the corresponding adjacency matrices, and the generating functions.

Document type: 
Thesis
Rights: 
Copyright remains with the author. The author granted permission for the file to be printed and for the text to be copied and pasted.
File(s): 
Supervisor(s): 
Marni Mishna
Lily Yen
Department: 
Science:
Thesis type: 
(Thesis) M.Sc.
Statistics: