A perimeter enumeration of column-convex polyominoes

Abstract : This work is concerned with the perimeter enumeration of column-convex polyominoes. We consider both the rectangular lattice and the hexagonal lattice. For the rectangular lattice, two formulas for the generating function (gf) already exist and, to all appearances, neither of them admits of a further simplification. We first rederive those two formulas (so as to make the paper self-contained), and then we enrich the rectangular lattice gf with some additional variables. That done, we make a change of variables, which (practically) produces the hexagonal lattice gf. This latter gf was first found by Lin and Wu in 1990. However, our present formula, in addition to having a simpler form, also allows a substantially easier Taylor series expansion. As to the methods, our one is descended from algebraic languages, whereas Lin and Wu used the Temperley methodology.
Document type :
Journal articles
Liste complète des métadonnées

Cited literature [15 references]  Display  Hide  Download

https://hal.inria.fr/hal-00966512
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Submitted on : Wednesday, March 26, 2014 - 4:59:31 PM
Last modification on : Saturday, October 6, 2018 - 7:34:01 PM
Document(s) archivé(s) le : Thursday, June 26, 2014 - 11:56:59 AM

File

471-2413-3-PB.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00966512, version 1

Collections

Citation

Svjetlan Feretić. A perimeter enumeration of column-convex polyominoes. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2007, 9 (1), pp.57--83. ⟨hal-00966512⟩

Share

Metrics

Record views

78

Files downloads

415