递归树的若干枚举特征

递归树由Meir和Moon定义作非平面增长树的一种，且所有节点出度都是允许的．本文首先在n个节点的递归树集合和n-1个元素的排列之间建立一个新的──对应，这个对应能同时给出树叶子和排列中的路段之间的对应和树叶子数和排列中的路段数之间的密切关系．同时还研究递归树的各种枚举特征，诸如节点的分类枚举（内节点和叶子节点、偶节点和奇节点，具不同出度的节点）和通路长度枚举（接各种节点分类）．

SOME ENUMERATION CHARACTERISTICS OF RECURSIVE TREES

Recursive tree is defined by Meir and Moon as the variety of non-planarincreasing tree such that all node degrees are allowed. This paper provides a 1-1 correspondence between recursive trees, with size n and leaf number k, and permutations, with size n-l and run number k.Various enumeration characteristics of recursive tree, such as classifying enumeration of nodes (internal nodes and leaves, even and odd nodes, nodes with different out-degrees) and path lengths (according to different node classifications) are investigated, and the corresponding exact enumerating formulas and asymptotic behaviour are given.