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

https://hal.inria.fr/hal-01185159
Contributor : Coordination Episciences Iam <>
Submitted on : Wednesday, August 19, 2015 - 11:42:39 AM
Last modification on : Thursday, May 11, 2017 - 1:02:52 AM
Long-term archiving on: : Friday, November 20, 2015 - 10:33:04 AM

File

dmAJ0110.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01185159, version 1

Collections

Citation

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. ⟨hal-01185159⟩

Share

Metrics

Record views

52

Files downloads

504