DMTCS Proceedings, Discrete Models: Combinatorics, Computation, and Geometry, DM-CCG 2001

Font Size:  Small  Medium  Large

A Bijection for Directed-Convex Polyominoes

Alberto Del Lungo, Massimo Mirolli, Renzo Pinzani, Simone Rinaldi

Abstract


In this paper we consider two classes of lattice paths on the plane which use north, east, south, and west unitary steps, beginning and ending at (0,0). We enumerate them according to the number of steps by means of bijective arguments; in particular, we apply the cycle lemma. Then, using these results, we provide a bijective proof for the number of directed-convex polyominoes having a fixed number of rows and columns.

Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page

Valid XHTML 1.0 Transitional