Refined enumeration of k-plane trees and k-noncrossing trees

DOI10.1007/S00026-023-00642-6MaRDI QIDQ6192068zbMATH OpenOpenAlexFDO

Authors

Publication date 11 March 2024

Published in Annals of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2205.01002

zbMATH Keywords

counting formula\(k\)-noncrossing treeslabelled noncrossing trees

Mathematics Subject Classification ID

Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10) Enumeration in graph theory (05C30) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Abstract: A $k$-plane tree is a plane tree whose vertices are assigned labels between $1$ and $k$ in such a way that the sum of the labels along any edge is no greater than $k+1$. These trees are known to be related to $(k+1)$-ary trees, and they are counted by a generalised version of the Catalan numbers. We prove a surprisingly simple refined counting formula, where we count trees with a prescribed number of labels of each kind. Several corollaries are derived from this formula, and an analogous theorem is proven for $k$-noncrossing trees, a similarly defined family of labelled noncrossing trees that are related to $(2k+1)$-ary trees.

Recommendations

• Enumeration of \(k\)-noncrossing trees and forests
• Bijections for a class of labeled plane trees
• Bijections for classes of labelled trees
• Counting vertices with given outdegree in plane trees and \(k\)-ary trees
• \((k,m)\)-Catalan numbers and hook length polynomials for plane trees

Cites work

• scientific article; zbMATH DE number 3961646 (Why is no real title available?)
• scientific article; zbMATH DE number 1268810 (Why is no real title available?)
• 2-noncrossing trees and 5-ary trees
• Bijections for a class of labeled plane trees
• Enumeration of \(k\)-noncrossing trees and forests
• Enumeration of generalized Dyck paths based on the height of down-steps modulo \(k\)
• Staircase tilings and \(k\)-Catalan structures
• Twelve countings with rooted plane trees

Cited in

(2)

• Bijections for classes of labelled trees
• Enumeration of \(k\)-noncrossing trees and forests

This page was built for publication: Refined enumeration of \(k\)-plane trees and \(k\)-noncrossing trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6192068)