Research ArticleOpen AccessGoogle Scholar indexed
Counting Types of Runs in Classes of Arborescent Words
Mathematics Institute, Free University of Berlin, Berlin, Germany
University of Quebec at Montreal, Montreal City, Canada
- 1 Mathematics Institute, Free University of Berlin, Berlin, Germany
- 2 University of Quebec at Montreal, Montreal City, Canada
Open Journal of Discrete Mathematics·Volume 03 (2013)·Pages 7–15·Published 29 January 2013·DOI10.4236/ojdm.2013.31002
Copy link · social · email
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.
KeywordsRunsStructured WordsTreelike StructuresCombinatorial SpeciesGenerating SeriesCycle Index Series
- W. Feller, “An Introduction to Probability Theory and Its Applications: Vol. I,” Third Edition, John Wiley & Sons Inc., New York, 1968.
- 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
- 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
- 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
- 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.
- 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
- 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.
- 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
- 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.
- 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.
- 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
- 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