engleski

A q-enumeration of convex polyominoes by the festoon approach

In 1938, Polya stated an identity involving the perimeter and area generating function for parallelogram polyominoes. To obtain that identity, Polya presumably considered festoons. A festoon (so named by Flajolet) is a closed path w which can be written as w = uv, where each step of u is either ( 1, 0) or (0, 1), and each step of v is either (-1, 0) or (0, -1). In this paper, we introduce four new festoon-like objects. As a result, we obtain explicit expressions (and not just identities) for the generating functions of parallelogram polyominoes, directed convex polyominoes, and convex polyominoes. (C) 2004 Elsevier B.V. All rights reserved.

Closed lattice path; Factorization; Enclosed region; Convex polyomino; Q-enumeration

nije evidentirano