A generating tree approach to k-nonnesting arc diagrams

Date created: 
2014-07-18
Identifier: 
etd8479
Keywords: 
Arc diagram
Generating tree
Generating function
Nestings
Crossings
Set partition
Permutation
Matching
Tangled diagram
Bijection
Asymptotics
Abstract: 

This thesis describes a strategy for exhaustively generating series information and enumerating combinatorial classes that can be represented using arc diagrams. We focus on k-nonnesting set partitions, permutations, matchings and tangled diagrams. Results are new functional equations, counting sequences, bijections and asymptotic results for these classes. Our key innovation is a generalized arc diagram in which arcs may have left endpoints, but not right endpoints, and our main tool is generating trees.

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: Department of Mathematics
Thesis type: 
(Dissertation) Ph.D.
Statistics: