Enumerating alternating tree families - Markus Kuba; Alois Panholzer (Discrete Mathematics & Theoretical Computer Science, 2008)
We study two enumeration problems for $up-down alternating trees$, i.e., rooted labelled trees $T$, where the labels $ v_1, v_2, v_3, …$ on every path starting at the root of $T$ satisfy $v_1 < v_2 > v_3 < v_4 > …$. First we consider various tree families of interest in combinatorics (such as unordered, ordered, $d$-ary and Motzkin trees) and study the number $T_n$ of different up-down alternating labelled trees of size $n$. We obtain for all tree families considered an implicit characterization of the exponential generating function $T(z)$ leading to asymptotic results of the coefficients $T_n$ for various tree families. Second we consider the particular family of up-down alternating labelled ordered trees and study the influence of such an alternating labelling to the average shape of the trees by analyzing the parameters $label of the root node$, $degree of the root node$ and $depth of a random node$ in a random tree of size $n$. This leads to exact enumeration results and limiting distribution results.