Abstract
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.
Similar content being viewed by others
References
Aigner M.: Catalan-like numbers and determinants. J. Combin. Theory Ser. A 87, 33–51 (1999)
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.
Bacchelli S., Barcucci E., Grazzini E., Pergola E.: Exhaustive generation of combinatorial objects using ECO. Acta Inform. 40(8), 585–602 (2004)
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)
Barcucci E., Frosini A., Rinaldi S.: On directed-convex polyominoes in a rectangle. Discrete Math. 298(1-3), 62–78 (2005)
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)
Barcucci E., Del Lungo A., Pergola E., Pinzani R.: A methodology for plane trees enumeration. Discrete Math. 180(1-3), 45–64 (1998)
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)
Brlek S., Duchi E., Pergola E., Rinaldi S.: On the equivalence problem for succession rules. Discrete Math. 298(1-3), 142–154 (2005)
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.
Deutsch E., Ferrari L., Rinaldi S.: Production matrices. Adv. Appl. Math. 34(1), 101–122 (2005)
E. Deutsch and L.W. Shapiro, Exponential Riordan matrices, in preparation.
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.
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.
Ferrari L., Pinzani R.: A linear operator approach to succession rules. Linear Algebra Appl. 348, 231–246 (2002)
Hoffman K., Kunze R.: Linear Algebra, 2nd Ed. Prentice-Hall, New Jersey (1971)
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)
Merlini D., Verri M.C.: Generating trees and proper Riordan arrays. Discrete Math. 218(1-3), 167–183 (2000)
P. Peart andW.-J.Woan, Generating functions via Hankel and Stieltjes matrices, J. Integer Seq. 3 (2) (2000) Article 00.2.1.
Rogers D.G.: Pascal triangles, Catalan numbers and renewal arrays. Discrete Math. 22(3), 301–310 (1978)
Shapiro L.W.: Bijections and the Riordan group. Theoret. Comput. Sci. 307(2), 403–413 (2003)
Shapiro L.W., Getu S., Woan W.-J., Woodson L.C.: The Riordan group. Discrete Appl. Math. 34(1-3), 229–239 (1991)
N.J.A. Sloane, The on-line encyclopedia of integer sequences, published electronically at http://www.research.att.com/~njas/sequences/.
Sprugnoli R.: Riordan arrays and combinatorial sums. Discrete Math. 132(1-3), 267–290 (1994)
Salomaa A., Soittola M.: Automata-Theoretic Aspects of Formal Power Series. Springer-Verlag, New York (1978)
West J.: Generating trees and the Catalan and Schröder numbers. Discrete Math. 146(1-3), 247–262 (1996)
West J.: Generating trees and forbidden subsequences. Discrete Math. 157(1-3), 363–374 (1996)
Author information
Authors and Affiliations
Corresponding author
Additional information
L. Ferrari and S. Rinaldi have been partially supported by MIUR project: Linguaggi formali e automi: metodi, modelli e applicazioni.
Rights and permissions
About this article
Cite this article
Deutsch, E., Ferrari, L. & Rinaldi, S. Production Matrices and Riordan Arrays. Ann. Comb. 13, 65–85 (2009). https://doi.org/10.1007/s00026-009-0013-1
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00026-009-0013-1