Enumeration of Almost‐Convex Polygons on the Square Lattice

I. G. Enting, A. J. Guttmann, L. B. Richmond, N. C. Wormald

Research output: Contribution to journalArticleResearchpeer-review

9 Citations (Scopus)

Abstract

We classify self‐avoiding polygons on the square lattice according to a concavity measure, m, where 2m is the difference between the number of steps in the polygon and the perimeter of the minimal rectangle bounding the polygon. We generate series expansions for the perimeter generating functions Sm(x) for polygons of concavity m. We analyze the series Sm(x) for m = 0 to 3. If Nm,n denotes the number of polygons of perimeter 2n and concavity m, with m = o(n1/2), we prove that Nm,n ˜ 22n−m−7nm+1/m!, and that the radius of convergence of the series counting all polygons with m = o(n) is equal to 1/4. Our numerical data leads us to conjecture that in fact (Formula Presented.) for m = o(n1/2), a result confirmed for m = 0 and 1.

Original languageEnglish
Pages (from-to)445-461
Number of pages17
JournalRandom Structures & Algorithms
Volume3
Issue number4
DOIs
Publication statusPublished - 1992
Externally publishedYes

Cite this