Enumerating alternating tree families - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Discrete Mathematics and Theoretical Computer Science Année : 2008

Enumerating alternating tree families

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.
Nous étudions deux problèmes de dénombrement d'$\textit{arbres alternés haut-bas}$ : par définition, ce sont des arbres munis d'une racine et tels que, pour tout chemin partant de la racine, les valeurs $v_1,v_2,v_3,\ldots$ associées aux nœuds du chemin satisfont la chaîne d'inégalités $v_1 < v_2 > v_3 < v_4 > \cdots$. D'une part, nous considérons diverses familles d'arbres intéressantes du point de vue de l'analyse combinatoire (comme les arbres de Motzkin, les arbres non ordonnés, ordonnés et $d$-aires) et nous étudions pour chaque famille le nombre total $T_n$ d'arbres alternés haut-bas de taille $n$. Nous obtenons pour toutes les familles d'arbres considérées une caractérisation implicite de la fonction génératrice exponentielle $T(z)$. Cette caractérisation nous renseigne sur le comportement asymptotique des coefficients $T_n$ de plusieurs familles d'arbres. D'autre part, nous examinons le cas particulier de la famille des arbres ordonnés : nous étudions l'influence de l'étiquetage alterné haut-bas sur l'allure générale de ces arbres en analysant trois paramètres dans un arbre aléatoire (valeur de la racine, degré de la racine et profondeur d'un nœud aléatoire). Nous obtenons alors des résultats en terme de distribution limite, mais aussi de dénombrement exact.
Fichier principal
Vignette du fichier
dmAJ0110.pdf (238 Ko) Télécharger le fichier
Origine : Fichiers éditeurs autorisés sur une archive ouverte
Loading...

Dates et versions

hal-01185159 , version 1 (19-08-2015)

Identifiants

Citer

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⟩

Collections

TDS-MACS
24 Consultations
520 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More