×

Succession rules and deco polyominoes. (English) Zbl 0962.05018

Authors’ abstract: 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.

MSC:

05B50 Polyominoes
05A15 Exact enumeration problems, generating functions
05A10 Factorials, binomial coefficients, combinatorial functions

Software:

OEIS

References:

[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. Zbl0944.05005 · Zbl 0944.05005 · doi:10.1080/10236199908808200
[2] E. Barcucci, A. Del Lungo and R. Pinzani, “Deco” polyominoes, permutations and random generation. Theoret. Comput. Sci.159 (1996) 29-42. Zbl0872.68177 · Zbl 0872.68177 · doi:10.1016/0304-3975(95)00199-9
[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. Zbl0858.05006 · Zbl 0858.05006 · doi:10.1016/0012-365X(95)00003-F
[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. Zbl0651.05027 · Zbl 0651.05027 · doi:10.1007/BF01788555
[6] M. Delest and X.G. Viennot, Algebraic languages and polyominoes enumeration. Theoret. Comput. Sci.34 (1984) 169-206. · Zbl 0985.68516 · doi:10.1016/0304-3975(84)90116-6
[7] R.L. Graham, D.E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley (1989). Zbl0668.00003 · Zbl 0668.00003
[8] F.K. Hwang and C.L. Mallows, Enumerating Nested and Consecutive Partitions. J. Combin. TheorySer. A70 (1995) 323-333. Zbl0819.05005 · Zbl 0819.05005 · doi:10.1016/0097-3165(95)90097-7
[9] D.E. Knuth, The Art of Computer Programming, Vol. 1: Fundamental Algorithms. Addison Wesley, Reading Mass (1968). Zbl0191.17903 · Zbl 0191.17903
[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. Zbl0612.05012 · Zbl 0612.05012
[11] T.W. Narayana, Sur les treillis formés par les partitions d’un entier. C.R. Acad. Sci. Paris240 (1955) 1188-1189. Zbl0064.12705 · Zbl 0064.12705
[12] N.J.A. Sloane and S. Plouffe, The encyclopedia of integer sequences. Academic Press (1995). Zbl0845.11001 · Zbl 0845.11001
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.