A new way of counting the column-convex polyominoes by perimeter

✍ Scribed by Svjetlan Feretić

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 447 KB
• Volume: 180
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/s0012-365x(97)00114-3

✦ Synopsis

We introduce a new class of plane figures: the sequences of tailed column-convex polyominoes (for short: stapoes). Let G(x, y) and l(x, y) denote the perimeter generating functions for columnconvex polyominoes and stapoes, respectively. It will be clear from the definitions that G(x, y) is a simple fraction of l(x, y). But this latter function can be DSV-computed by solving just one quadratic equation (and not a system of quadratic equations). Thus the formula for G(x, y) can be obtained with ease.

R~um~

Nous introduisons une nouvelle classe de figures planaires: les chaines de polyominos verticalement convexes. Soient G(x, y) et l(x, y) les s6ries g6n6ratrices selon le p6rim6tre des polyominos verticalement convexes et des eha~nes de polyominos verticalement convexes respectivement. II sera clair, d'aprbs les d6finitions, que G(x, y) est une fraction rationnelle simple de I(x, y). Mais cette s6rie peut-6tre calcul6e par la m&hode DSV en r6solvant une seule 6quation quadratique (et non un syst~me de telles 6quations). On obtient ainsi ais6ment l'expression de G(x, y).