The height of multiple edge plane trees

DOI10.1007/S00010-015-0380-0MaRDI QIDQ291297zbMATH OpenOpenAlexWikidataFDO

Authors Clemens Heuberger, Helmut Prodinger, Stephan Wagner

Publication date 7 June 2016

Published in Aequationes Mathematicae (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

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)

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.

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

Cites work

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

Cited in

(5)

• Retakh's Motzkin paths and some combinatorial comments
• Enumeration of partial Łukasiewicz paths
• Batcher's odd-even exchange revisited: a generating functions approach
• Enumerations of plane trees with multiple edges and Raney lattice paths
• Partial skew Dyck paths: a kernel method approach

Describes a project that uses

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)