Succession rules and Deco polyominoes

Elena Barcucci; Sara Brunetti; Francesco Del Ristoro

RAIRO - Theoretical Informatics and Applications (2010)

  • Volume: 34, Issue: 1, page 1-14
  • ISSN: 0988-3754

Abstract

top
In this paper, we examine the class of "deco" polyominoes and the succession rule describing their construction. These polyominoes are enumerated according to their directed height by factorial numbers. By changing some aspects of the "factorial" rule, we obtain some succession rules that describe various "deco" polyomino subclasses. By enumerating the subclasses according to their height and width, we find the following well-known numbers: Stirling numbers of the first and second kind, Narayana and odd index Fibonacci numbers. We wish to point out how the changes made on the original succession rule yield some new succession rules that produce transcendental, algebraic and rational generating functions.

How to cite

top

Barcucci, Elena, Brunetti, Sara, and Ristoro, Francesco Del. " Succession rules and Deco polyominoes." RAIRO - Theoretical Informatics and Applications 34.1 (2010): 1-14. <http://eudml.org/doc/221961>.

@article{Barcucci2010,
abstract = { In this paper, we examine the class of "deco" polyominoes and the succession rule describing their construction. These polyominoes are enumerated according to their directed height by factorial numbers. By changing some aspects of the "factorial" rule, we obtain some succession rules that describe various "deco" polyomino subclasses. By enumerating the subclasses according to their height and width, we find the following well-known numbers: Stirling numbers of the first and second kind, Narayana and odd index Fibonacci numbers. We wish to point out how the changes made on the original succession rule yield some new succession rules that produce transcendental, algebraic and rational generating functions. },
author = {Barcucci, Elena, Brunetti, Sara, Ristoro, Francesco Del},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Polyomino; enumeration; succession rule; generating function combinatorial interpretation.; deco polyominoes; succession rules; Stirling numbers; Narayana and odd index Fibonacci numbers; generating functions},
language = {eng},
month = {3},
number = {1},
pages = {1-14},
publisher = {EDP Sciences},
title = { Succession rules and Deco polyominoes},
url = {http://eudml.org/doc/221961},
volume = {34},
year = {2010},
}

TY - JOUR
AU - Barcucci, Elena
AU - Brunetti, Sara
AU - Ristoro, Francesco Del
TI - Succession rules and Deco polyominoes
JO - RAIRO - Theoretical Informatics and Applications
DA - 2010/3//
PB - EDP Sciences
VL - 34
IS - 1
SP - 1
EP - 14
AB - In this paper, we examine the class of "deco" polyominoes and the succession rule describing their construction. These polyominoes are enumerated according to their directed height by factorial numbers. By changing some aspects of the "factorial" rule, we obtain some succession rules that describe various "deco" polyomino subclasses. By enumerating the subclasses according to their height and width, we find the following well-known numbers: Stirling numbers of the first and second kind, Narayana and odd index Fibonacci numbers. We wish to point out how the changes made on the original succession rule yield some new succession rules that produce transcendental, algebraic and rational generating functions.
LA - eng
KW - Polyomino; enumeration; succession rule; generating function combinatorial interpretation.; deco polyominoes; succession rules; Stirling numbers; Narayana and odd index Fibonacci numbers; generating functions
UR - http://eudml.org/doc/221961
ER -

References

top
  1. E. Barcucci, A. Del Lungo, E. Pergola and R. Pinzani, ECO: A methodology for the Enumeration of Combinatorial Objects. J. Differ. Equations Appl.5 (1999) 435-490.  
  2. E. Barcucci, A. Del Lungo and R. Pinzani, ``Deco'' polyominoes, permutations and random generation. Theoret. Comput. Sci.159 (1996) 29-42.  
  3. M. Bousquet-Mélou, q-énumération de polyominos convexes. Publication du LACIM, No. 9 Montréal (1991).  
  4. M. Bousquet-Mélou, A method for enumeration of various classes of column-convex polygons. Discrete Math.151 (1996) 1-25.  
  5. M. Delest, D. Gouyou-Beauchamps and B. Vauquelin, Enumeration of parallelogram polyominoes with given bound and site perimeter. Graphs Combin.3 (1987) 325-339.  
  6. M. Delest and X.G. Viennot, Algebraic languages and polyominoes enumeration. Theoret. Comput. Sci.34 (1984) 169-206.  
  7. R.L. Graham, D.E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley (1989).  
  8. F.K. Hwang and C.L. Mallows, Enumerating Nested and Consecutive Partitions. J. Combin. TheorySer. A70 (1995) 323-333.  
  9. D.E. Knuth, The Art of Computer Programming, Vol. 1: Fundamental Algorithms. Addison Wesley, Reading Mass (1968).  
  10. G. Kreweras, Joint distributions of three descriptive parameters of bridges, edited by G. Labelle and P. Leroux, Combinatoire Énumérative, Montréal 1985. Springer, Berlin, Lecture Notes in Math.1234 (1986) 177-191.  
  11. T.W. Narayana, Sur les treillis formés par les partitions d'un entier. C.R. Acad. Sci. Paris240 (1955) 1188-1189.  
  12. N.J.A. Sloane and S. Plouffe, The encyclopedia of integer sequences. Academic Press (1995).  

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.