Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, EpiSciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Conference papers

Enumerating alternating tree families

Abstract : 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.
Complete list of metadata

Cited literature [9 references]  Display  Hide  Download
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Wednesday, August 19, 2015 - 11:42:39 AM
Last modification on : Wednesday, October 13, 2021 - 7:58:04 PM
Long-term archiving on: : Friday, November 20, 2015 - 10:33:04 AM


Publisher files allowed on an open archive




Markus Kuba, Alois Panholzer. Enumerating alternating tree families. 20th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2008), 2008, Viña del Mar, Chile. pp.105-116, ⟨10.46298/dmtcs.3624⟩. ⟨hal-01185159⟩



Record views


Files downloads