A Combinatorial Analysis of Tree-Like Sentences

Gilbert Labelle^1*, Louise Laforest²

¹Département de Mathématiques, Université du Québec à Montréal, Montreal, Canada.
²Département d’Informatique, Université du Québec à Montréal, Montreal, Canada.

DOI: 10.4236/ojdm.2015.53004                

Abstract

A sentence over a finite alphabet A, is a finite sequence of non-empty words over A. More generally, we define a graphical sentence over A by attaching a non-empty word over A to each arrow and each loop of a connected directed graph (digraph, for short). Each word is written according to the direction of its corresponding arrow or loop. Graphical sentences can be used to encode sets of sentences in a compact way: the readable sentences of a graphical sentence being the sentences corresponding to directed paths in the digraph. We apply combinatorial equations on enriched trees and rooted trees, in the context of combinatorial species and Pólya theories, to analyze parameters in classes of tree-like sentences. These are graphical sentences constructed on tree-like digraphs.

Keywords

Pólya Theory, Combinatorial Species, Digraphs, Tree-Like Sentences

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Bergeron, F., Labelle, G. and Leroux, P. (1998) Combinatorial Species and Tree-Like Structures (Encyclopedia of Mathematics and Its Applications). Cambridge University Press, Cambridge.
[2]	Labelle, G. (1992) Counting Asymmetric Enriched Trees. Journal of Symbolic Computation, 14, 211-242. http://dx.doi.org/10.1016/0747-7171(92)90037-5
[3]	Pólya, G. and Read, R.C. (1987) Combinatorial Enumeration of Groups, Graphs and Chemical Compounds. Springer-Verlag, Berlin, Heidelberg, and New-York.
[4]	Décoste, H., Labelle, G. and Leroux, P. (1982) Une approche combinatoire pour l’itération de Newton-Raphson. Advances in Applied Mathematics, 3, 407-416. http://dx.doi.org/10.1016/S0196-8858(82)80013-4
[5]	Joyal. A. (1981) Une théorie combinatoire des séries formelles. Advances in Mathematics, 42, 1-82. http://dx.doi.org/10.1016/0001-8708(81)90052-9
[6]	Labbé, J.-P. and Labelle, G. (2013) Counting Types of Runs in Classes of Arborescent Words. Open Journal of Discrete Mathematics, 3, 7-15. http://dx.doi.org/10.4236/ojdm.2013.31002
[7]	Leroux, P. and Miloudi, B. (1992) Généralisations de la formule d’Otter. Annales des Sciences Mathématiques du Québec, 16, 53-80.
[8]	Labelle, G. (1986) Some New Computational Methods in the Theory of Species. In: Labelle, G. and Leroux, P., Eds., Combinatoire Enumérative, Lecture Notes in Mathematics 1234, Springer Berlin Heidelberg, Berlin, 192-209. http://dx.doi.org/10.1007/bfb0072517
[9]	Labelle, G. (1981) Une nouvelle démonstration combinatoire des formules d’inversion de Lagrange. Advances in Mathematics, 42, 217-247. http://dx.doi.org/10.1016/0001-8708(81)90041-4
[10]	Pivoteau, C., Salvy, B. and Soria, M. (2012) Algorithms for Combinatorial Structures: Well-Founded Systems and Newton Iterations. Journal of Combinatorial Theory, Series A, 119, 1711-1773. http://dx.doi.org/10.1016/j.jcta.2012.05.007
[11]	Décoste, H., Labelle, G. and Leroux, P. (1992) The Functorial Composition of Species, a Forgotten Operation. Discrete Mathematics, 99, 31-48. http://dx.doi.org/10.1016/0012-365X(92)90363-K