2017/06/30 by Michael Wallner
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Arithmetic #Bijection #Bijection, injection and surjection #Binary number #Binary search tree #Binary tree #Biology #Combinatorics #Computer science #Construct (python library) #Data Management and Algorithms #Discrete mathematics #Geometry #Interpretation (philosophy) #Limit (mathematics) #Mathematics #Plane (geometry) #Root (linguistics) #Sequence (biology) #Stochastic processes and statistical mechanics #Tree (set theory) #Weight-balanced tree #cs.DM #math.CO #msc:05A15 #msc:05A19 #msc:05C30
paper · pdf · doi:10.1016/j.tcs.2018.06.053
17 pages, 10 figures, 2 tables
openalex created_date 2017/06/30 · openalex publication_date 2018/07/05 · arxiv created 2018/07/11 · arxiv updated 2018/07/12 · openalex updated_date 2026/08/05
Plane increasing trees are rooted labeled trees embedded into the plane such that the sequence of labels is increasing on any branch starting at the root. Relaxed binary trees are a subclass of unlabeled directed acyclic graphs. We construct a bijection between these two combinatorial objects and study the therefrom arising connections of certain parameters. Furthermore, we show central limit theorems for two statistics on leaves. We end the study by considering more than 20 subclasses and their bijective counterparts. Many of these subclasses are enumerated by known counting sequences, and thus enrich their combinatorial interpretation.