Counting Types of Runs in Classes of Arborescent Words

Jean-Philippe Labbé, Gilbert Labelle

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

DOI: 10.4236/ojdm.2013.31002                

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

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	W. Feller, “An Introduction to Probability Theory and Its Applications: Vol. I,” Third Edition, John Wiley & Sons Inc., New York, 1968.
[2]	A. M. Mood, “The Distribution Theory of Runs,” Annals of Mathematical Statistics, Vol. 11, No. 4, 1940, pp. 367-392. doi:10.1214/aoms/1177731825
[3]	M. V. Koutras, G. K. Papadopoulos and S. G. Papastavridis, “Runs on a Circle,” Journal of Applied Probability, Vol. 32, No. 2, 1995, pp. 396-404. doi:10.2307/3215295
[4]	A. Joyal, “Une Théorie Combinatoire des Séries Formelles,” Advances in Mathematics, Vol. 42, No. 1, 1981, pp. 1-82. doi:10.1016/0001-8708(81)90052-9
[5]	A. Joyal, “Foncteurs Analytiques et Espèces de Structures,” In: Combinatoire énumérative (Montreal, Quebec, 1985), Vol. 1234 of Lecture Notes in Mathematics, Springer, Berlin, 1986, pp. 126-159.
[6]	G. Labelle, “Une Nouvelle Démonstration Combinatoire des Formules D'inversion de Lagrange,” Advances in Mathematics, Vol. 42, No. 3, 1981, pp. 217-247. doi:10.1016/0001-8708(81)90041-4
[7]	F. Bergeron, G. Labelle and P. Leroux, “Combinatorial species and tree-like structures, Vol. 67 of Encyclopedia of Mathematics and its Applications,” Cambridge University Press, Cambridge, 1998.
[8]	G. Labelle, “éclosions Combinatoires Appliquées à L'inversion Multidimensionnelle des Séries Formelles,” Journal of Combinatorial Theory, Series A, Vol. 39, No. 1, 1985, pp. 52-82. doi:10.1016/0097-3165(85)90083-4
[9]	G. Labelle, “Some New Computational Methods in the Theory of Species,” In Combinatoire énumérative Lecture Notes in Mathematics Vol. 1234, Springer, Berlin, 1986, pp. 192-209.
[10]	P. Erd?s and P. Révész, “On the Length of the Longest Head-Run,” In Topics in Information Theory (Second Colloq., Keszthely, 1975), Colloquia Mathematica Societatis János Bolyai, Vol. 16, North-Holland, Amsterdam, 1977, pp. 219-228.
[11]	L. J. Guibas and A. M. Odlyzko, “Long Repetitive Patterns in Random Sequences,” Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete, Vol. 53, No. 3, 1980, pp. 241-262. doi:10.1007/BF00531434
[12]	Y. Kong, “Distribution of Runs and Longest Runs: A New Generating Function Approach,” Journal of the American Statistical Association, Vol. 101, No. 475, 2006, pp. 1253-1263. doi:10.1198/016214505000001401