Enumerating alternating tree familiesReportar como inadecuado




Enumerating alternating tree families - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 Institut für Diskrete Mathematik und Geometrie Wien

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 $Tz$ 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.

Résumé : 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 $Tz$. 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.

Keywords : Alternating trees Generating functions Functional equations Asymptotic enumeration results





Autor: Markus Kuba - Alois Panholzer -

Fuente: https://hal.archives-ouvertes.fr/



DESCARGAR PDF




Documentos relacionados