Counting Types of Runs in Classes of Arborescent Words - Open Journal of Discrete Mathematics

OJDM > Vol.3 No.1, January 2013

Counting Types of Runs in Classes of Arborescent Words ()

HTML

Download as PDF (Size: 536KB) PP. 7-15

DOI: 10.4236/ojdm.2013.31002 3,967 Downloads 6,324 Views Citations

Author(s)

Jean-Philippe Labbé, Gilbert Labelle

Affiliation(s)

Mathematics Institute, Free University of Berlin, Berlin, Germany.
University of Quebec at Montreal, Montreal City, Canada.

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.

KEYWORDS

Runs; Structured Words; Treelike Structures; Combinatorial Species; Generating Series; Cycle Index Series

Share and Cite:

J. Labbé and G. Labelle, "Counting Types of Runs in Classes of Arborescent Words," Open Journal of Discrete Mathematics, Vol. 3 No. 1, 2013, pp. 7-15. doi: 10.4236/ojdm.2013.31002.

Journals Menu

Follow SCIRP

	+1 323-425-8868
	customer@scirp.org
	+86 18163351462(WhatsApp)
	1655362766

	Paper Publishing WeChat

Journals Menu

Home

About SCIRP

Service

Policies