A Combinatorial Analysis of Tree-Like Sentences

• 作者: Gilbert Labelle Louise Laforest
• 来源期刊: 离散数学期刊(英文)
• 学科: 数学
• 关键词: Pólya THEORY Combinatorial SPECIES DIGRAPHS Tree-Like SENTENCES
• 年，卷（期）: 2015,（3）
• 页码范围: 32-53
• 页数: 22页
• 分类号: O1

摘要

A sentence over a finite alphabet A, is a finite sequence of non-empty words over A. More generally, we define a graphical sentence over A by attaching a non-empty word over A to each arrow and each loop of a connected directed graph (digraph, for short). Each word is written according to the direction of its corresponding arrow or loop. Graphical sentences can be used to encode sets of sentences in a compact way: the readable sentences of a graphical sentence being the sentences corresponding to directed paths in the digraph. We apply combinatorial equations on enriched trees and rooted trees, in the context of combinatorial species and Pólya theories, to analyze parameters in classes of tree-like sentences. These are graphical sentences constructed on tree-like digraphs.