The vertical profile of embedded trees

MaRDI QIDQ456391zbMATH OpenFDO

Authors Mireille Bousquet-Mélou, Guillaume Chapuy

Publication date 24 October 2012

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1203.4148, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v19i3p46

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

enumerationembedded trees

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Exact enumeration problems, generating functions (05A15) Enumeration in graph theory (05C30)

Abstract: Consider a rooted binary tree with n nodes. Assign with the root the abscissa 0, and with the left (resp. right) child of a node of abscissa i the abscissa i-1 (resp. i+1). We prove that the number of binary trees of size n having exactly n_i nodes at abscissa i, for l =< i =< r (with n = sum_i n_i), is ${\displaystyle }$ frac{n_0}{n_l n_r} {{n_{-1}+n_1} choose {n_0-1}} prod_{lle ile r atop i ot = 0}{{n_{i-1}+n_{i+1}-1} choose {n_i-1}}, ${\displaystyle }$ with n_{l-1}=n_{r+1}=0. The sequence (n_l, ..., n_{-1};n_0, ..., n_r) is called the vertical profile of the tree. The vertical profile of a uniform random tree of size n is known to converge, in a certain sense and after normalization, to a random mesure called the integrated superbrownian excursion, which motivates our interest in the profile. We prove similar looking formulas for other families of trees whose nodes are embedded in Z. We also refine these formulas by taking into account the number of nodes at abscissa j whose parent lies at abscissa i, and/or the number of vertices at abscissa i having a prescribed number of children at abscissa j, for all i and j. Our proofs are bijective.

Recommendations

• The density of the ISE and local limit laws for embedded trees
• On the profile of random trees
• The profile of unlabeled trees
• Profiles of random trees: Plane-oriented recursive trees
• Profiles of random trees: plane-oriented recursive trees

Cited in

(6)

• Limit laws for embedded trees: Applications to the integrated superBrownian excursion
• A note on naturally embedded ternary trees
• The watering of tall trees -- embolization and recovery
• The density of the ISE and local limit laws for embedded trees
• Distances between pairs of vertices and vertical profile in conditioned Galton-Watson trees
• Counting trees using symmetries

This page was built for publication: The vertical profile of embedded trees

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