Naslov
A q-enumeration of convex polyominoes by the festoon approach

Autori
Feretić, Svjetlan

Izvornik
Theoretical Computer Science (0304-3975) 319 (2004); 333-356

Vrsta, podvrsta i kategorija rada
Radovi u časopisima, članak, znanstveni

Ključne riječi
Closed lattice path; Factorization; Enclosed region; Convex polyomino; Q-enumeration

Sažetak
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.

Izvorni jezik
Engleski

Znanstvena područja
Matematika

POVEZANOST RADA