The area generating function for simplex-duplex polyominoes - Mathematics > CombinatoricsReportar como inadecuado

The area generating function for simplex-duplex polyominoes - Mathematics > Combinatorics - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Abstract: Back in the early days of polyomino enumeration, a model called column-convexpolyominoes was introduced and its area generating function was found. Thatgenerating function is rational: the numerator has degree four and thedenominator has degree three. Let a column-duplex polyomino be a polyominowhose columns can have either one or two connected components. A simplex-duplexpolyomino is a column-duplex polyomino in which there is no occurrence of twoadjacent columns each having two connected components. Simplex-duplexpolyominoes are not easy to deal with, but their area generating function canstill be found. To find this generating function, we use an upgraded version ofthe Temperley method. Though that technique is widely used in these times, ourapplication presents two interesting features. Firstly, we add one or twocolumns at a time, thus bypassing those simplex-duplex polyominoes which endwith a two-component column. It is somewhat more usual to add just one columnat a time. Secondly, we obtain a functional equation that involves both thefirst and the second derivatives of the sought-for generating function. Suchequations usually involve the first derivative only. In some cases, noderivative is involved at all. Right because of this latter interestingfeature, the Temperley method produces a very complicated formula for thegenerating function. Anyway, from that formula it is easy to compute Taylorpolynomials. Thus we get plenty of evidence that the number of n-celledsimplex-duplex polyominoes behaves asymptotically as 0.119443*3.522020^n. Forcomparison, the number of n-celled column-convex polyominoes behavesasymptotically as 0.180916*3.205569^n.

Autor: Svjetlan Feretic


Documentos relacionados