Protected Branches in Ordered Trees
- 1 January 2023
- journal article
- research article
- Published by Global Science Press in Journal of Mathematical Study
- Vol. 56 (1) , 1-17
Abstract
In this paper, we consider the class of ordered trees and its two subclasses, bushes and planted trees, which consist of the ordered trees with root degree at least $2$ and with root degree $1$ respectively. In these three classes, we study the number of trees of size $n$ with $k$ protected (resp. unprotected) branches, and the total number of branches (resp. protected branches, unprotected branches) among all trees of size $n$. The explicit formulas as well as the generating functions are obtained. Furthermore, we find that, in each class, as $n$ goes to infinity, the proportion of protected branches among all branches in all trees of size $n$ approaches $ 1/3$. ordered tree, bush, planted tree, protected branch, unprotected branch, Catalan number, generating function. 05A10, 05A15, 05A16, 05C05 COPYRIGHT: © Global Science Press yanglinmath@l63.com (Lin Yang) slyang@lut.cn (Shengliang Yang)