Counting Types of Runs in Classes of Arborescent Words


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 sizek, linear runs, etc) are studied in the context of R-enriched arborescent words, where R is a given species of structures.

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.

Conflicts of Interest

The authors declare no conflicts of interest.


[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

Copyright © 2021 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.