Some combinatorial problems on ordered trees (Q1065013)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Some combinatorial problems on ordered trees |
scientific article |
Statements
Some combinatorial problems on ordered trees (English)
0 references
1983
0 references
The ordered trees of this paper are more commonly known as rooted plane trees. For the class of ordered trees on n vertices, the author determines the total number of leaves (nonroot vertices of degree 1), the sum of the lengths of all paths from a root to a leaf, and the sum of the lengths of all paths from a root to a vertex. Since it is known that the number of different ordered trees on n vertices is \(\frac{1}{n}\left( \begin{matrix} 2n-2\\ n-1\end{matrix} \right)\), it follows that averages may be computed for the class. In particular, this yields another proof of the author's earlier result that the average number of leaves of ordered trees on n vertices is \(\frac{n}{2}\). The author's assertion that ''the average path length may be considered as the average height of random ordered trees with n nodes'' seems to be nonstandard.
0 references
ordered trees
0 references
rooted plane trees
0 references
path length
0 references