Exact generating function for 2-convex polygons

DOI10.1088/1751-8113/41/5/055001MaRDI QIDQ5443435zbMATH OpenOpenAlexWikidataFDO

Authors W. R. G. James, I. Jensen, Anthony J Guttmann

Publication date 21 February 2008

Published in Journal of Physics A: Mathematical and Theoretical (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0805.1259

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Generalized quadrangles and generalized polygons in finite geometry (51E12) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Classical equilibrium statistical mechanics (general) (82B05) Random walks, random surfaces, lattice animals, etc. in equilibrium statistical mechanics (82B41)

Abstract: Polygons are described as almost-convex if their perimeter differs from the perimeter of their minimum bounding rectangle by twice their `concavity index', $m$. Such polygons are called emph{$m$-convex} polygons and are characterised by having up to $m$ indentations in their perimeter. We first describe how we conjectured the (isotropic) generating function for the case $m=2$ using a numerical procedure based on series expansions. We then proceed to prove this result for the more general case of the full anisotropic generating function, in which steps in the $x$ and $y$ direction are distinguished. In so doing, we develop tools that would allow for the case $m>2$ to be studied. %In our proof we use a `divide and conquer' approach, factorising 2-convex %polygons by extending a line along the base of its indents. We then use %the inclusion-exclusion principle, the Hadamard product and extensions to %known methods to derive the generating functions for each case.

Recommendations

• Families of \(m\)-convex polygons: \(m=1\)
• Enumeration of Almost-Convex Polygons on the Square Lattice
• On the number of convex polyominoes.
• Exact solution of the row-convex polygon perimeter generating function
• Rigorous result for the area-weighted moments of convex polygons on the square lattice

Cited in

(2)

• Families of \(m\)-convex polygons: \(m=1\)
• Rigorous result for the area-weighted moments of convex polygons on the square lattice

This page was built for publication: Exact generating function for 2-convex polygons

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5443435)