The distribution of height and diameter in random non-plane binary trees

DOI10.1002/rsa.20393zbMath1250.05095arXiv1009.1515MaRDI QIDQ3165458

Nicolas Broutin, Philippe Flajolet

Publication date: 26 October 2012

Published in: Random Structures & Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

height; generating function; limiting distribution; singularity analysis; random tree; non-plane unlabelled binary trees; Otter trees

Mathematics Subject Classification ID

05C05: Trees

05C80: Random graphs (graph-theoretic aspects)

Related Items

The metric space of limit laws for $q$-hook formulas, The degree profile of random Pólya trees, Scaling limits of Markov branching trees with applications to Galton-Watson and random unordered trees, Normal limiting distribution of the size of binary interval trees, Two results about the Sackin and Colless indices for phylogenetic trees and their shapes, Model spaces of regularity structures for space-fractional SPDEs, Extremal statistics on non-crossing configurations, Asymptotic properties of random unlabelled block-weighted graphs

Uses Software

• OEIS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Mellin transforms and asymptotics: Harmonic sums
• Scaling limits of Markov branching trees with applications to Galton-Watson and random unordered trees
• The continuum random tree. I
• Asymptotic densities in logic and type theory
• Random trees and applications
• The average height of binary trees and other simple trees
• Functionals of Brownian meander and Brownian excursion
• On Ramanujan's \(Q\)-function
• The continuum random tree. III
• The number of trees
• The height of random binary unlabelled trees
• The Random Walk Construction of Uniform Spanning Trees and Uniform Labelled Trees
• The Enumeration of Trees by Height and Diameter
• Isomorphism and Symmetries in Random Phylogenetic Trees
• Random Trees
• The Galton-Watson process conditioned on the total progeny
• The distribution of the maximum Brownian excursion
• On the Altitude of Nodes in Random Trees
• The Distribution of Heights of Binary Trees and Other Simple Trees
• Some typical properties of large AND/OR Boolean formulas
• And/Or Trees Revisited
• The CRT is the scaling limit of unordered binary trees
• On the height of trees
• Parking functions, empirical processes, and the width of rooted labeled trees