Counting Types of Runs in Classes of Arborescent Words

• 作者: Gilbert Labelle Jean-Philippe Labbé
• 来源期刊: 离散数学期刊(英文)
• 学科: 数学
• 关键词: RUNS Structured WORDS Treelike Structures Combinatorial Species GENERATING SERIES Cycle Index SERIES
• 年，卷（期）: 2013,（1）
• 页码范围: 7-15
• 页数: 9页
• 分类号: O1

摘要

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.