Some combinatorial problems on ordered trees
type: Item
instance of: scholarly article
title: Some combinatorial problems on ordered trees
zbMATH Open document ID: 0576.05016
author: Zheng Yu Wang
published in: Chinese Annals of Mathematics. Series B
publication date: 1983-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05A15
zbMATH DE Number: 3920490
zbMATH Keywords: ordered trees
zbMATH Keywords: rooted plane trees
zbMATH Keywords: path length
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 3920490