The height of multiple edge plane trees

DOI10.1007/S00010-015-0380-0zbMATH Open1337.05055arXiv1503.04749OpenAlexW1942124093WikidataQ59463244 ScholiaQ59463244MaRDI QIDQ291297FDOQ291297

Authors: Clemens Heuberger, Helmut Prodinger, Stephan Wagner 

Publication date: 7 June 2016

Published in: Aequationes Mathematicae (Search for Journal in Brave)

Abstract: Multi-edge trees as introduced in a recent paper of Dziemia'nczuk are plane trees where multiple edges are allowed. We first show that $d$-ary multi-edge trees where the out-degrees are bounded by $d$ are in bijection with classical $d$-ary trees. This allows us to analyse parameters such as the height. The main part of this paper is concerned with multi-edge trees counted by their number of edges. The distribution of the number of vertices as well as the height are analysed asymptotically.

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

Recommendations

• Counting vertices with given outdegree in plane trees and \(k\)-ary trees
• scientific article; zbMATH DE number 1439405
• Enumerations of plane trees with multiple edges and Raney lattice paths
• Deterministic edge weights in increasing tree families
• Some properties of planar trees with a hanging root

zbMATH Keywords

limit distributionsheight\(d\)-ary treemulti-edge treeplane tree

Mathematics Subject Classification ID

Trees (05C05) Exact enumeration problems, generating functions (05A15) Combinatorial probability (60C05) Planar graphs; geometric and topological aspects of graph theory (05C10) Asymptotic enumeration (05A16) Enumeration in graph theory (05C30)

Cites Work

• Analytic combinatorics
• On convergence rates in the central limit theorems for combinatorial structures
• Singularity Analysis of Generating Functions
• Random Trees
• Mellin transforms and asymptotics: Harmonic sums
• The average height of binary trees and other simple trees
• Title not available (Why is that?)
• The Distribution of Heights of Binary Trees and Other Simple Trees
• Mathematics for the Analysis of Algorithms.
• The average height of planted plane trees with M leaves
• The average height of r-tuply rooted planted plane trees
• A note on a result of R. Kemp on r-tuply rooted planted plane trees
• Title not available (Why is that?)
• Register Allocation for Unary–Binary Trees
• Enumerations of plane trees with multiple edges and Raney lattice paths
• Title not available (Why is that?)
• A lattice of combinatorial Hopf algebras, Application to binary trees with multiplicities

Cited In (4)

• Retakh's Motzkin paths and some combinatorial comments
• Enumeration of partial Łukasiewicz paths
• Batcher's odd-even exchange revisited: a generating functions approach
• Partial skew Dyck paths: a kernel method approach

Uses Software

• OEIS

This page was built for publication: The height of multiple edge plane trees

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