Discrete Mathematics & Theoretical Computer Science |

- 1 Institut für Diskrete Mathematik und Geometrie [Wien]

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$.

Source: HAL:hal-01184684v1

Volume: DMTCS Proceedings vol. AG, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities

Section: Proceedings

Published on: January 1, 2006

Imported on: May 10, 2017

Keywords: increasing trees,label-based parameters,limiting distribution,[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS],[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO]

This page has been seen 323 times.

This article's PDF has been downloaded 164 times.