Enumerating alternating tree families

Kuba, Markus ; Panholzer, Alois

Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AJ, 20th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2008), DMTCS Proceedings vol. AJ, 20th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2008) (2008).

Résumé

We study two enumeration problems for $\textit{up-down alternating trees}$, i.e., rooted labelled trees $T$, where the labels $ v_1, v_2, v_3, \ldots$ on every path starting at the root of $T$ satisfy $v_1 < v_2 > v_3 < v_4 > \cdots$. 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 $\textit{label of the root node}$, $\textit{degree of the root node}$ and $\textit{depth of a random node}$ in a random tree of size $n$. This leads to exact enumeration results and limiting distribution results.

Détail

DOI : 10.46298/dmtcs.3624