Skip to main content
Log in

Production Matrices and Riordan Arrays

  • Published:
Annals of Combinatorics Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Similar content being viewed by others

References

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

    Article  MATH  MathSciNet  Google Scholar 

  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. Bacchelli S., Barcucci E., Grazzini E., Pergola E.: Exhaustive generation of combinatorial objects using ECO. Acta Inform. 40(8), 585–602 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  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)

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  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)

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  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)

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  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. Deutsch E., Ferrari L., Rinaldi S.: Production matrices. Adv. Appl. Math. 34(1), 101–122 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  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.

    Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

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

    MATH  Google Scholar 

  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)

    MATH  MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

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

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

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

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

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

    Article  MATH  MathSciNet  Google Scholar 

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

    MATH  Google Scholar 

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

    Article  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Simone Rinaldi.

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

Reprints 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

Download citation

  • Received:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00026-009-0013-1

Keywords

AMS Subject Classification

Navigation