In this paper we consider a restricted class of polyominoes that we call Z-convex polyominoes. Z-convex polyominoes are polyominoes such that any two pairs of cells can be connected by a monotone path making at most two turns (like the letter Z). This class of convex polyominoes appears to resist standard decompositions, so we propose a construction by “inflation” that allows to write a system of functional equations for their generating functions. The generating function P(t) of Z-convex polyominoes with respect to the semi-perimeter turns out to be algebraic all the same and surprisingly, like the generating function of convex polyominoes, it can be expressed as a rational function of t and the generating function of Catalan numbers.

Duchi, E., Rinaldi, S., & Schaeffer, G. (2008). The number of Z-convex polyominoes. ADVANCES IN APPLIED MATHEMATICS, 40(1), 54-72 [10.1016/j.aam.2006.07.004].

The number of Z-convex polyominoes

Rinaldi, S.;
2008

Abstract

In this paper we consider a restricted class of polyominoes that we call Z-convex polyominoes. Z-convex polyominoes are polyominoes such that any two pairs of cells can be connected by a monotone path making at most two turns (like the letter Z). This class of convex polyominoes appears to resist standard decompositions, so we propose a construction by “inflation” that allows to write a system of functional equations for their generating functions. The generating function P(t) of Z-convex polyominoes with respect to the semi-perimeter turns out to be algebraic all the same and surprisingly, like the generating function of convex polyominoes, it can be expressed as a rational function of t and the generating function of Catalan numbers.
Duchi, E., Rinaldi, S., & Schaeffer, G. (2008). The number of Z-convex polyominoes. ADVANCES IN APPLIED MATHEMATICS, 40(1), 54-72 [10.1016/j.aam.2006.07.004].
File in questo prodotto:
File Dimensione Formato  
z-convex.pdf

non disponibili

Tipologia: PDF editoriale
Licenza: NON PUBBLICO - Accesso privato/ristretto
Dimensione 744.82 kB
Formato Adobe PDF
744.82 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11365/35952
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo