On the distribution of depths in increasing trees
The electronic journal of combinatorics, Tome 17 (2010)
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.
DOI :
10.37236/409
Classification :
05A19, 05C05, 60C05
Mots-clés : increasing trees, depth of nodes
Mots-clés : increasing trees, depth of nodes
@article{10_37236_409,
author = {Markus Kuba and Stephan Wagner},
title = {On the distribution of depths in increasing trees},
journal = {The electronic journal of combinatorics},
year = {2010},
volume = {17},
doi = {10.37236/409},
zbl = {1204.05023},
url = {http://geodesic.mathdoc.fr/articles/10.37236/409/}
}
Markus Kuba; Stephan Wagner. On the distribution of depths in increasing trees. The electronic journal of combinatorics, Tome 17 (2010). doi: 10.37236/409
Cité par Sources :