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

DOI10.1007/S00026-023-00642-6arXiv2205.01002OpenAlexW4382772270MaRDI QIDQ6192068FDOQ6192068

Authors:

Publication date: 11 March 2024

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Staircase tilings and \(k\)-Catalan structures
• Enumeration of \(k\)-noncrossing trees and forests
• Twelve countings with rooted plane trees
• Title not available (Why is that?)
• Bijections for a class of labeled plane trees
• 2-noncrossing trees and 5-ary trees
• Enumeration of generalized Dyck paths based on the height of down-steps modulo \(k\)

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)