Skip to Main content Skip to Navigation
Conference papers

Label-based parameters in increasing trees

Abstract : Grown simple families of increasing trees are a subclass of increasing trees, which can be constructed by an insertion process. Three such tree families contained in the grown simple families of increasing trees are of particular interest: $\textit{recursive trees}$, $\textit{plane-oriented recursive trees}$ and $\textit{binary increasing trees}$. Here we present a general approach for the analysis of a number of label-based parameters in a random grown simple increasing tree of size $n$ as, e.g., $\textit{the degree of the node labeled j}$, $\textit{the subtree-size of the node labeled j}$, etc. Further we apply the approach to the random variable $X_{n,j,a}$, which counts the number of size-$a$ branches attached to the node labeled $j$ (= subtrees of size $a$ rooted at the children of the node labeled $j$) in a random grown simple increasing tree of size $n$. We can give closed formulæ for the probability distribution and the factorial moments. Furthermore limiting distribution results for $X_{n,j,a}$ are given dependent on the growth behavior of $j=j(n)$ compared to $n$.
Complete list of metadata

Cited literature [9 references]  Display  Hide  Download

https://hal.inria.fr/hal-01184684
Contributor : Coordination Episciences Iam <>
Submitted on : Monday, August 17, 2015 - 2:22:58 PM
Last modification on : Thursday, May 11, 2017 - 1:02:51 AM
Long-term archiving on: : Wednesday, November 18, 2015 - 10:44:30 AM

File

dmAG0123.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01184684, version 1

Collections

Citation

Markus Kuba, Alois Panholzer. Label-based parameters in increasing trees. Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities, 2006, Nancy, France. pp.321-330. ⟨hal-01184684⟩

Share

Metrics

Record views

68

Files downloads

485