The vertical profile of embedded trees
type: Item
instance of: scholarly article
title: The vertical profile of embedded trees
zbMATH Open document ID: 1253.05081
author: Mireille Bousquet-Mélou
author: Guillaume Chapuy
published in: The Electronic Journal of Combinatorics
publication date: 2012-10-24T00:00:00Z
full work available at URL: https://arxiv.org/abs/1203.4148
full work available at URL: v19i3p46
review text: Summary: 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 \leq i \leq r\) (with \(n = \sum_i n_i)\), is \[ \frac{n_0}{n_l n_r} {{n_{-1}+n_1} \choose {n_0-1}} \prod_{l\leq i\leq r \atop i\not = 0}{{n_{i-1}+n_{i+1}-1} \choose {n_i-1}}, \] with \(n_{l-1}=n_{r+1}=0\). The sequence \((n_l, \dots, n_{-1};n_0, \dots 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.
Mathematics Subject Classification ID: 05C30
Mathematics Subject Classification ID: 05A15
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C80
zbMATH DE Number: 6098388
zbMATH Keywords: enumeration
zbMATH Keywords: embedded trees
MaRDI profile type: Publication
arXiv ID: 1203.4148
description: scientific article; zbMATH DE number 6098388