Convex polyominoes, general polyominoes, and self-avoiding walks using algebraic languages
Anthony Arthur Mikovsky · Scholarly Commons (University of Pennsylvania) · 1997
Beginning with a transfer matrix method used by R. C. Read to find the number of all polyominoes with at most a given number of rows, this method will be reinterpreted in several different ways. First, this transfer matrix method is redefined for convex polyominoes to find a few generating functions for convex polyominoes with some small number of rows. These transfer matrices are then reinterpreted in the form of an algebraic language which simplifies the computations. Finally for the convex polyomino problem, connections are found between the row sizes and a generating function is found for the number of all convex polyominoes enumerated according to area, width, height, and perimeter. In an examination of general polyominoes, Read's transfer matrices are interpreted using an algebraic languages and by this interpretation, exact generating functions are found for polyominoes having 2, 3 and 4 rows. Also in the discussion of general polyominoes, programs are given to find large transfer matrices of numbers where the largest eigenvalue is the growth constant for the generating function. Approximations of these eigenvalues are found for 5, 6, 7 and 8 rows. Finally the same algebraic language interpretation is given for a similar self-avoiding walk problem. The number of SAWs with a restriction on the maximum difference in the first position of the lattice points is found. By using the same technique as was used for general polyominoes, generating functions are given for SAWs with height at most 2 and 3 and the growth constants are given for a height of 4, 5 and 6.