ON NODE ENUMERATION AND NODE PATH LENGTH OF ORDERED TREES

Abstract Considering the class Γ( n, m ) of ordered trees with m leaves and n - m internal nodes, a set of generating functions are established for the following problems: (1) the total number nodes with degree r over Γ( n , m ), (2) the total path length of nodes over Γ( n , m ), and (3) the total number of nodes over Γ( n, m ) on level k . Some particular counting fomulas are derived from them.