A Generating Tree Approach to <Emphasis Type="Italic">k</Emphasis>-Nonnesting Partitions and Permutations |
| |
Authors: | Sophie Burrill Sergi Elizalde Marni Mishna Lily Yen |
| |
Institution: | 1.Department of Mathematics,Simon Fraser University,Burnaby,Canada;2.Department of Mathematics,Dartmouth College,Hanover,USA;3.Department of Mathematics and Statistics,Capilano University,North Vancouver,Canada |
| |
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 which uses 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. Key to the solution is a superset of diagrams that permit semi-arcs. Many of the resulting counting sequences also count other well-known objects, such as Baxter permutations, and Young tableaux of bounded height. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|