<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 13 Issue 1" %>
Production Matrices and Riordan Arrays
Emeric Deutsch1, Luca Ferrari2, and Simone Rinaldi3
1Department of Mathematics, Polytechnic University, Six Metrotech Center, Brooklyn, New York 11201, USA
2Dipartimento di Sistemi e Informatica, Universit\`{a} degli Studi di Firenze, Viale Morgagni 65, 50134 Firenze, Italy
3Dipartimento di Scienze Matematiche e Informatiche ``Roberto Magari'', Universit\`{a} Degli Studi di Siena, Pian dei Mantellini, 44, 53100 Siena, Italy
Annals of Combinatorics 13 (1) pp.65-85 March, 2009
AMS Subject Classification: 05A15, 05C38
We translate the concept of succession rule and the ECO method into matrix notation, introducing the concept of \emph{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.
Keywords: ECO method, production matrices, Riordan arrays


1. M. Aigner, Catalan-like numbers and determinants, J. Combin. Theory Ser. A 87 (1999) 33–-51.

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.

3. S. Bacchelli, E. Barcucci, E. Grazzini, and E. Pergola, Exhaustive generation of combinatorial objects using ECO, Acta Inform. 40 (8) (2004) 585-–602.

4. C. Banderier, M. Bousquet-M´elou, A. Denise, P. Flajolet, D. Gardy, and D. Gouyou- Beauchamps, Generating functions for generating trees, Discrete Math. 246 (1-3) (2002) 29–-55.

5. E. Barcucci, A. Frosini, and S. Rinaldi, On directed-convex polyominoes in a rectangle, Discrete Math. 298 (1-3) (2005) 62–-78.

6. E. Barcucci, A. Del Lungo, E. Pergola, and R. Pinzani, ECO: a methodology for the enumeration of combinatorial objects, J. Differ. Equations Appl. 5 (4-5) (1999) 435-–490.

7. E. Barcucci, A. Del Lungo, E. Pergola, and R. Pinzani, A methodology for plane trees enumeration, Discrete Math. 180 (1-3) (1998) 45–-64.

8. E. Barcucci, A. Del Lungo, E. Pergola, and R. Pinzani, Random generation of trees and other combinatorial objects, Theoret. Comput. Sci. 218 (2) (1999) 219–-232.

9. S. Brlek, E. Duchi, E. Pergola, and S. Rinaldi, On the equivalence problem for succession rules, Discrete Math. 298 (1-3) (2005) 142-–154.

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.

11. E. Deutsch, L. Ferrari, and S. Rinaldi, Production matrices, Adv. Appl. Math. 34 (1) (2005) 101–-122.

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.

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.

15. L. Ferrari and R. Pinzani, A linear operator approach to succession rules, Linear Algebra Appl. 348 (2002) 231–-246.

16. K. Hoffman and R. Kunze, Linear Algebra, 2nd Ed., Prentice-Hall, New Jersey, 1971.

17. D. Merlini, D.G. Rogers, R. Sprugnoli, and M.C. Verri, On some alternative characterizations of Riordan arrays, Canad. J. Math. 49 (2) (1997) 301-–320.

18. D. Merlini and M.C. Verri, Generating trees and proper Riordan arrays, Discrete Math. 218 (1-3) (2000) 167-–183.

19. P. Peart andW.-J.Woan, Generating functions via Hankel and Stieltjes matrices, J. Integer Seq. 3 (2) (2000) Article 00.2.1.

20. D.G. Rogers, Pascal triangles, Catalan numbers and renewal arrays, Discrete Math. 22 (3) (1978) 301-–310.

21. L.W. Shapiro, Bijections and the Riordan group, Theoret. Comput. Sci. 307 (2) (2003) 403–-413.

22. L.W. Shapiro, S. Getu, W.-J. Woan, and L.C. Woodson, The Riordan group, Discrete Appl. Math. 34 (1-3) (1991) 229-–239.

23. N.J.A. Sloane, The on-line encyclopedia of integer sequences, published electronically at http://www.research.att.com/~njas/sequences/.

24. R. Sprugnoli, Riordan arrays and combinatorial sums, Discrete Math. 132 (1-3) (1994) 267–-290.

25. A. Salomaa and M. Soittola, Automata-Theoretic Aspects of Formal Power Series, Springer-Verlag, New York, 1978.

26. J.West, Generating trees and the Catalan and Schr¨oder numbers, Discrete Math. 146 (1-3) (1996) 247-–262.

27. J. West, Generating trees and forbidden subsequences, Discrete Math. 157 (1-3) (1996) 363–-374.