2022/05/02 by Isaac Owino Okoth, Okoth, Isaac Owino, Stephan M. Wagner +1
Mathematics · #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Markov Chains and Monte Carlo Methods
paper · pdf · doi:10.48550/arxiv.2205.01002
openalex publication_date 2022/05/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.