On the distribution of depths in increasing trees (Q612916)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the distribution of depths in increasing trees |
scientific article |
Statements
On the distribution of depths in increasing trees (English)
0 references
16 December 2010
0 references
Summary: By a theorem of Dobrow and Smythe, the depth of the \(k\)th node in very simple families of increasing trees (which includes, among others, binary increasing trees, recursive trees and plane ordered recursive trees) follows the same distribution as the number of edges of the form \(j-(j+1)\) with \(j<k\). In this short note, we present a simple bijective proof of this fact, which also shows that the result actually holds within a wider class of increasing trees. We also discuss some related results that follow from the bijection as well as a possible generalization. Finally, we use another similar bijection to determine the distribution of the depth of the lowest common ancestor of two nodes.
0 references
increasing trees
0 references
depth of nodes
0 references