Protected Branches in Ordered Trees

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