HAL: hal-00019885, version 1

arXiv: math.CO/0602124

Detailed view

Export this paper BibTeX - EndNote - TEI - RefWorks -

The number of Z-convex polyominoes

Enrica Duchi 1, Simone Rinaldi 2, Gilles Schaeffer 3

(2006)

In this paper we consider a restricted class of convex 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). In particular they are convex polyominoes, but they appear to resist standard decompositions. 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.

1:	Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA)
	CNRS : UMR7089 – Université Paris VII - Paris Diderot
2:	Department of Mathematics and Computer Science / Dipartimento di Scienze Matematiche e Informatiche "Roberto Magari" (DSMI)
	Università degli studi di Siena – University of Siena
3:	Laboratoire d'informatique de l'école polytechnique (LIX)
	CNRS : UMR7161 – Polytechnique - X

Subject

:

Mathematics/Combinatorics

hal-00019885, version 1

http://hal.archives-ouvertes.fr/hal-00019885

oai:hal.archives-ouvertes.fr:hal-00019885

From: Enrica Duchi <>

Submitted on: Tuesday, 28 February 2006 19:37:55

Updated on: Tuesday, 3 July 2007 13:00:42