OJDM  Vol.3 No.1 , January 2013
Counting Types of Runs in Classes of Arborescent Words
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.
Cite this paper: 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.

[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