×

zbMATH — the first resource for mathematics

Production matrices and riordan arrays. (English) Zbl 1229.05015
Summary: We translate the concept of succession rule and the ECO method into matrix notation, introducing the concept of production matrix. This allows us to combine our method with other enumeration techniques using matrices, such as the method of Riordan matrices. Finally we treat the case of rational production matrices, i.e., those leading to rational generating functions.

MSC:
05A15 Exact enumeration problems, generating functions
Software:
OEIS
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Aigner M.: Catalan-like numbers and determinants. J. Combin. Theory Ser. A 87, 33–51 (1999) · Zbl 0929.05004 · doi:10.1006/jcta.1998.2945
[2] M. Aigner, Catalan and other numbers: a recurrent theme, In: Algebraic Combinatorics and Computer Science, H. Crapo and D. Senato, Eds., Springer-Verlag, New York, (2001) pp. 347–390. · Zbl 0971.05002
[3] Bacchelli S., Barcucci E., Grazzini E., Pergola E.: Exhaustive generation of combinatorial objects using ECO. Acta Inform. 40(8), 585–602 (2004) · Zbl 1090.68555
[4] Banderier C., Bousquet-Mèlou M., Denise A., Flajolet P., Gardy D., Gouyou-Beauchamps D.: Generating functions for generating trees. Discrete Math. 246(1-3), 29–55 (2002) · Zbl 0997.05007 · doi:10.1016/S0012-365X(01)00250-3
[5] Barcucci E., Frosini A., Rinaldi S.: On directed-convex polyominoes in a rectangle. Discrete Math. 298(1-3), 62–78 (2005) · Zbl 1070.05024 · doi:10.1016/j.disc.2005.01.006
[6] Barcucci E., Del Lungo A., Pergola E., Pinzani R.: ECO: a methodology for the enumeration of combinatorial objects. J. Differ. Equations Appl. 5(4-5), 435–490 (1999) · Zbl 0944.05005 · doi:10.1080/10236199908808200
[7] Barcucci E., Del Lungo A., Pergola E., Pinzani R.: A methodology for plane trees enumeration. Discrete Math. 180(1-3), 45–64 (1998) · Zbl 0904.05004 · doi:10.1016/S0012-365X(97)00122-2
[8] Barcucci E., Del Lungo A., Pergola E., Pinzani R.: Random generation of trees and other combinatorial objects. Theoret. Comput. Sci. 218(2), 219–232 (1999) · Zbl 0916.68124 · doi:10.1016/S0304-3975(98)00322-3
[9] Brlek S., Duchi E., Pergola E., Rinaldi S.: On the equivalence problem for succession rules. Discrete Math. 298(1-3), 142–154 (2005) · Zbl 1070.05005 · doi:10.1016/j.disc.2004.07.019
[10] A. Del Lungo, A. Frosini, and S. Rinaldi, ECO method and the exhaustive generation of convex polyominoes, In: Discrete Mathematics and Theoretical Computer Science, Lecture Notes in Computer Science, S. Calude, M.J. Dinneen, and V. Vajnovski, Eds., Springer, Berlin, (2003) pp. 129–140. · Zbl 1038.68084
[11] Deutsch E., Ferrari L., Rinaldi S.: Production matrices. Adv. Appl. Math. 34(1), 101–122 (2005) · Zbl 1064.05012 · doi:10.1016/j.aam.2004.05.002
[12] E. Deutsch and L.W. Shapiro, Exponential Riordan matrices, in preparation.
[13] E. Duchi, A. Frosini, R. Pinzani, and S. Rinaldi, A note on rational succession rules, J. Integer Seq. 6 (1) (2003) Article 03.1.7. · Zbl 1013.05007
[14] L. Ferrari, E. Pergola, R. Pinzani, and S. Rinaldi, An algebraic characterization of the set of succession rules, Theoret. Comput. Sci. 281 (1-2) (2002) 351–367. · Zbl 1021.68068
[15] Ferrari L., Pinzani R.: A linear operator approach to succession rules. Linear Algebra Appl. 348, 231–246 (2002) · Zbl 1003.05007 · doi:10.1016/S0024-3795(01)00584-5
[16] Hoffman K., Kunze R.: Linear Algebra, 2nd Ed. Prentice-Hall, New Jersey (1971) · Zbl 0212.36601
[17] Merlini D., Rogers D.G., Sprugnoli R., Verri M.C.: On some alternative characterizations of Riordan arrays. Canad. J. Math. 49(2), 301–320 (1997) · Zbl 0886.05013 · doi:10.4153/CJM-1997-015-x
[18] Merlini D., Verri M.C.: Generating trees and proper Riordan arrays. Discrete Math. 218(1-3), 167–183 (2000) · Zbl 0949.05004 · doi:10.1016/S0012-365X(99)00343-X
[19] P. Peart andW.-J.Woan, Generating functions via Hankel and Stieltjes matrices, J. Integer Seq. 3 (2) (2000) Article 00.2.1. · Zbl 0961.15018
[20] Rogers D.G.: Pascal triangles, Catalan numbers and renewal arrays. Discrete Math. 22(3), 301–310 (1978) · Zbl 0398.05007 · doi:10.1016/0012-365X(78)90063-8
[21] Shapiro L.W.: Bijections and the Riordan group. Theoret. Comput. Sci. 307(2), 403–413 (2003) · Zbl 1048.05008 · doi:10.1016/S0304-3975(03)00227-5
[22] Shapiro L.W., Getu S., Woan W.-J., Woodson L.C.: The Riordan group. Discrete Appl. Math. 34(1-3), 229–239 (1991) · Zbl 0754.05010 · doi:10.1016/0166-218X(91)90088-E
[23] N.J.A. Sloane, The on-line encyclopedia of integer sequences, published electronically at http://www.research.att.com/\(\sim\)njas/sequences/ . · Zbl 1274.11001
[24] Sprugnoli R.: Riordan arrays and combinatorial sums. Discrete Math. 132(1-3), 267–290 (1994) · Zbl 0814.05003 · doi:10.1016/0012-365X(92)00570-H
[25] Salomaa A., Soittola M.: Automata-Theoretic Aspects of Formal Power Series. Springer-Verlag, New York (1978) · Zbl 0377.68039
[26] West J.: Generating trees and the Catalan and Schröder numbers. Discrete Math. 146(1-3), 247–262 (1996) · Zbl 0841.05002 · doi:10.1016/0012-365X(94)00067-1
[27] West J.: Generating trees and forbidden subsequences. Discrete Math. 157(1-3), 363–374 (1996) · Zbl 0877.05002 · doi:10.1016/S0012-365X(96)83023-8
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.