A generating tree approach to k-nonnesting partitions and permutations

Abstract

We describe a generating tree approach to the enumeration and exhaustive generation of k-nonnesting set partitions and permutations. Unlike previous work in the literature using the connections of these objects to Young tableaux and restricted lattice walks, our approach deals directly with partition and permutation diagrams. We provide explicit functional equations for the generating functions, with k as a parameter.

35 pages, 14 figures, 3 tables, Maple code in appendix

References in corpus (5)

• Bijections for Baxter Families and Related Objects
• Random $k$-noncrossing RNA Structures
• Counting permutations with no long monotone subsequence via generating trees and the kernel method
• Crossings and Nestings for Arc-Coloured Permutations
• Set partitions with no m-nesting

Cited by in corpus (4)

• Tableau sequences, open diagrams, and Baxter families
• Set partitions with no m-nesting
• A Baxter class of a different kind, and other bijective results using tableau sequences ending with a row shape
• Constructing Skolem sequences via generating trees