Motzkin树上的保护点的计数问题

Enumeration of Protected Nodes in Motzkin Trees

中文关键词:  Motzkin树  保护点  Motzkin数  二元发生函数  Lagrange求逆公式

英文关键词:Motzkin trees  protected nodes  Motzkin number  Bivariate generating function  Lagrange inversion

中文摘要:

      本文根据Motzkin树的叶点、与叶点相邻的顶点、保护点、(保护)分支点和(保护)孤立点的个数对Motzkin树进行计数;得到了相应的发生函数和直接公式;发现了当$n$趋于无穷大时,在$n$个边的Motzkin树中受保护的分支点和孤立点在顶点中所占比例分别为$\frac{4}{27}$和$\frac{2}{9}$.

英文摘要:

      In this paper, we enumerate the set of Motzkin trees with $n$ edges according to the number of leaves, the number of vertices adjacent to a leaf, the number of protected nodes, the number of (protected) branch nodes, and the number of (protected) lonely nodes. Explicit formulae as well as generating functions are obtained. We also find that, as $n$ goes to infinity, the proportion of protected branch nodes and protected lonely nodes among all vertices of Motzkin trees with $n$ edges approaches $4/27$ and $2/9$.