TITLE:
Counting Types of Runs in Classes of Arborescent Words
AUTHORS:
Jean-Philippe Labbé, Gilbert Labelle
KEYWORDS:
Runs; Structured Words; Treelike Structures; Combinatorial Species; Generating Series; Cycle Index Series
JOURNAL NAME:
Open Journal of Discrete Mathematics,
Vol.3 No.1,
January
29,
2013
ABSTRACT: An arborescence is a directed rooted tree in which all edges point away from the root. An arborescent word is obtained by replacing each element of the underlying set of an arborescence by an arbitrary letter of a given alphabet (with possible repetitions). We define a run in an arborescent word as a maximal sub-arborescent word whose letters are all identical. Various types of runs (e.g., runs of size ≤ k, linear runs, etc) are studied in the context of R-enriched arborescent words, where R is a given species of structures.