Name
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 abiscissa i, for l <= i <= r (with n - Sigma(i)n(i)), is n(0)/n(l)n(r) ((n0 -1) (n-1 + n1)) Pi (l <= i <= r i not equal 0) ((ni-1) n(i-1) (+) n(i+1 -1)) 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 ramdom 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. |
Year | Venue | Keywords |
|---|---|---|
2012 | ELECTRONIC JOURNAL OF COMBINATORICS | Enumeration,Embeddedtrees |
Field | DocType | Volume |
Random tree,Discrete mathematics,Combinatorics,Bijection,Abscissa,Vertex (geometry),Enumeration,Binary tree,Excursion,Mathematics | Journal | 19.0 |
Issue | ISSN | Citations |
3.0 | 1077-8926 | 1 |
PageRank | References | Authors |
0.38 | 4 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mireille Bousquet-mélou | 1 | 421 | 56.28 |
| Guillaume Chapuy | 2 | 73 | 11.25 |