Level number sequences for trees (Q1096638): Difference between revisions

Define the level of a node v in a rooted tree t as the number of nodes on the chain connecting v to the root of t (including both end nodes). The level number sequence of a tree t describes the numbers \(n_ 1,n_ 2,..\). of nodes at the different levels 1,2,.... Considering binary trees with n binary nodes, let \(H_ n\) be the number of different level number sequences that occur. The authors give a precise asymptotic estimate of the form \(H_ n\sim K\cdot \alpha\) n, where K and \(\alpha\) are complicated constants. The result is obtained via a residue analysis of the generating function and the use of a non-standard form of so-called q-series. Since the generating function of this problem also appears in connection with Poincaré series in algebraic topology, the result seems to be highly interesting.