Volume 56, Issue 1
Protected Branches in Ordered Trees

Lin Yang & Shengliang Yang

J. Math. Study, 56 (2023), pp. 1-17.

Published online: 2022-11

Export citation
  • 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$.

  • AMS Subject Headings

05A10, 05A15, 05A16, 05C05

  • Copyright

COPYRIGHT: © Global Science Press

  • Email address

yanglinmath@l63.com (Lin Yang)

slyang@lut.cn (Shengliang Yang)

  • BibTex
  • RIS
  • TXT
@Article{JMS-56-1, author = {Yang , Lin and Yang , Shengliang}, title = {Protected Branches in Ordered Trees}, journal = {Journal of Mathematical Study}, year = {2022}, volume = {56}, number = {1}, pages = {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$.

}, issn = {2617-8702}, doi = {https://doi.org/10.4208/jms.v56n1.23.01}, url = {http://global-sci.org/intro/article_detail/jms/21217.html} }
TY - JOUR T1 - Protected Branches in Ordered Trees AU - Yang , Lin AU - Yang , Shengliang JO - Journal of Mathematical Study VL - 1 SP - 1 EP - 17 PY - 2022 DA - 2022/11 SN - 56 DO - http://doi.org/10.4208/jms.v56n1.23.01 UR - https://global-sci.org/intro/article_detail/jms/21217.html KW - ordered tree, bush, planted tree, protected branch, unprotected branch, Catalan number, generating function. AB -

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

Lin Yang & Shengliang Yang. (2022). Protected Branches in Ordered Trees. Journal of Mathematical Study. 56 (1). 1-17. doi:10.4208/jms.v56n1.23.01
Copy to clipboard
The citation has been copied to your clipboard