Applications in Enumerative Combinatorics of Infinite Weighted Automata and Graphs

Published in Volume XXIV, Issue 1, 2014, pages 137-171, doi: 10.7561/SACS.2014.1.137

Authors: R. De Castro, A. Ramírez, J.L. Ramírez

Abstract

In this paper, we present a general methodology to solve a wide variety of classical lattice path counting problems in a uniform way. These counting problems are related to Dyck paths, Motzkin paths and some generalizations. The methodology uses weighted automata, equations of ordinary generating functions and continued fractions. This new methodology is called Counting Automata Methodology. It is a variation of the technique proposed by Rutten, which is called Coinductive Counting.

Full Text (PDF)

References

[1] A. V. Aho, R. Sethi, and J. D. Ullman. Compilers: Principles, Techniques and Tools. Addison-Wesley, Reading, MA, 1986.

[2] E. Barcucci, E. Pergola, R. Pinzani, and S. Rinaldi. ECO method and hill-free generalized Motzkin paths. Séminaire Lotharingien de Combinatoire, 46:1–14, 2001.

[3] F. Bernhart. Catalan, Motzkin, and Riordan numbers. Discrete Mathematics, 204(1-3):73–112, 1999. http://dx.doi.org/10.1016/S0012-365X(99)00054-0

[4] J. Berstel, L. Boasson, O. Carton, and I. Fagnot. Sturmian trees. Theory of Computing Systems, 46(3):443–478, 2010. http://dx.doi.org/10.1007/s00224-009-9228-0

[5] V. Berthé and M. Rigo. Combinatorics, Automata and Number Theory. Encyclopedia of Mathematics and its Applications, Cambridge, 2010.

[6] M. Bousquet-Mélou. Algebraic generating functions in enumerative combinatorics and context-free languages. In: V. Diekert and B. Durand, editors, STACS 2005, volume 3404 of Lecture Notes in Computer Science, pages 18–35, Springer, Heidelberg, 2005. http://dx.doi.org/10.1007/978-3-540-31856-9_2

[7] P. Brändén and T. Mansour. Finite automata and pattern avoidance in words. Journal of Combinatorial Theory, Series A, 110(1):127–145, 2005. http://dx.doi.org/10.1016/j.jcta.2004.10.007 .

[8] W. Chen. Context-free grammars, differential operators and formal power series. Theoretical Computer Sciences, 117(1-2):113–129, 1993. http://dx.doi.org/10.1016/0304-3975(93)90307-F

[9] W. Chen, S. Yan, and L. Yang. Identities from weighted Motzkin paths. Advances in Applied Mathematics, 41(3):329–334, 2008. http://dx.doi.org/10.1016/j.aam.2004.11.007

[10] M. Delest. Algebraic languages: a bridge between combinatorics and computer science. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 24:71–88, 1996.

[11] E. Deutsch, E. Munarini, and S. Rinaldi. Skew Dyck paths. Journal of Statistical Planning and Inference, 140(8):2191–2203, 2010. http://dx.doi.org/10.1016/j.jspi.2010.01.015

[12] E. Deutsch and L. Shapiro. A bijection between ordered trees and 2-Motzkin paths and its many consequences. Discrete Mathematics, 256(3):655–670, 2002. http://dx.doi.org/10.1016/S0012-365X(02)00341-2

[13] M. Droste, W. Kuich, and H. Vogler. Handbook of Weighted Automata, first edition, Springer, Monographs in Theoretical Computer Science, 2009.

[14] P. Flajolet. Combinatorial aspects of continued fractions. Discrete Mathematics, 32(2):125–161, 1980. http://dx.doi.org/10.1016/0012-365X(80)90050-3

[15] P. Flajolet and R. Sedgewick. Analytic Combinatorics, Cambridge, 2009.

[16] R. Graham, M. Grötschel, and L. Lovász. Handbook of Combinatorics, volume 2, MIT Press, Cambridge, 1995.

[17] R. Graham, D. Knuth, and O. Patashnik. Concrete Mathematics, second ediction, Addison-Wesley, 1994.

[18] T. Mansour. Combinatorics of Set Partitions. Discrete Mathematics and its Applications, CRC Press, 2012.

[19] J. E. Hopcroft, R. Motwani, and J. D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading, MA, 2001.

[20] A. Lascoux. Symmetric Functions and Combinatorial Operators on Polynomials. CBMS Regional Conference Series in Mathematics, American Mathematical Society, 2003.

[21] S. Heubach and T. Mansour. Combinatorics of Compositions and Words. Discrete Mathematics and its Applications, CRC Press, 2010.

[22] T. Mansour and A. O. Munagi. Enumeration of gap-bounded set partitions. Journal of Automata, Languages and Combinatorics, 14(3- 4):237–245, 2009.

[23] T. Mansour and A. Vainshtein. Restricted permutations and Chebyshev polynomials. Seminaire Lotharingien de Combinatoire, 47 Article B47c:(2002).

[24] T. Noe. On the Divisibility of Generalized Central Trinomial Coefficients. Journal of Integer Sequences, 9(2):1–12, 2006.

[25] J. M. Rutten. Coinductive counting with weighted automata. Journal of Automata, Languages and Combinatorics, 8(2):319–352, 2003.

[26] J. Sakarovitch. Elements of Automata Theory, Cambridge, 2009.

[27] A. Sapounakis and P. Tsikouras. On k-colored Motzkin words. Journal of Integer Sequences, 7(2):1–13, 2004.

[28] J. Shallit. A Second Course in Formal Languages and Automata Theory. Cambridge, 2009.

[29] L. Shapiro and C. Wang. A Bijection Between 3-Motzkin Paths and Schröder Paths With No Peak at Odd Height. Journal of Integer Sequences, 12(3):1–9, 2009.

[30] N. J. A. Sloane. The On-Line Encyclopedia of Integer Sequences. https://oeis.org/ .

[31] K. Uchimura. Properties of structure generating functions of automata and their applications for linear systems. Theoretical Computer Science, 18(2):207–220, 1982. http://dx.doi.org/10.1016/0304-3975(82)90022-6

[32] K. Uchimura. Truncations of infinite matrices and algebraic series with some CF grammars. Theoretical Computer Science, 31(3):227–261, 1984. doi:10.1016/0304-3975(84)90035-5

[33] W. Woan. Animals and 2-Motzkin Paths. Journal of Integer Sequences, 8(5):1–12, 2005.

Bibtex

@article{sacscuza:de2014aiecoiwaag,
  title={Applications in Enumerative Combinatorics of Infinite Weighted Automata and Graphs},
  author={R. De Castro and A. Ram'{i}rez and J.L. Ram'{i}rez},
  journal={Scientific Annals of Computer Science},
  volume={24},
  number={1},
  organization={``A.I. Cuza'' University, Iasi, Romania},
  year={2014},
  pages={137--171},
  doi={10.7561/SACS.2014.1.137},
  publisher={``A.I. Cuza'' University Press}
}