A convex polyomino (sometimes called a "convex polygon") is a polyomino whose perimeter is equal to that of its minimal bounding box (Bousquet-Mélou et al. 1999). If it furthemore contains at least one corner of its minimal bounding box, it is said to be a directed convex polyomino. A column-convex polyomino is a self-avoiding polyomino such that the intersection of any vertical line with the polyomino has at most two connected components, and a row-convex polyomino is similarly defined. A number of types of named convex polyominoes are depicted above (Bousquet-Mélou et al. 1999).
Klarner and Rivest (1974) and Bender (1974) gave the asymptotic estimate for the number of convex polyominoes having area as
(1)
with and (Delest and Viennot 1984).
The anisotropic perimeter and area generating function
(2)
where is the number of polygons with horizonal bonds, vertical bonds, and area is given by
(3)
where
and is the polynomial recurrence relation
(6)
with and (Bousquet-Mélou 1992b). The first few of these polynomials are given by
Expanding the generating function shows that the number of convex polyominoes having perimeter is given by
(11)
where , , and is a binomial coefficient (Delest and Viennot 1984, Bousquet-Mélou 1992ab). The generating function for is explicitly given by
(12)
(Delest and Viennot 1984; Guttmann and Enting 1988). The first few terms are therefore 1, 2, 7, 28, 120, 528, 2344, 10416, ... (OEIS A005436).
This function has been computed exactly for the column-convex and directed column-convex polyominoes (Bousquet-Mélou 1996, Bousquet-Mélou et al. 1999). is a q-series, but becomes algebraic for column-convex polyominoes. However, for column-convex polyominoes again involves q-series (Temperley 1956, Bousquet-Mélou et al. 1999).
is an algebraic function of and (called the "fugacities") given by
where
(Lin and Chang 1988, Bousquet-Mélou 1992ab). This can be solved to explicitly give
(18)
(Gessel 2000, Bousquet-Mélou 1992ab).
satisfies the inversion relation
(19)
where
(Lin and Chang 1988, Bousquet-Mélou et al. 1999).
The half-vertical perimeter and area generating function for column-convex polyominos of width 3 is given by the special case
(22)
of the general rational function (Bousquet-Mélou et al. 1999), which satisfies the reciprocity relation
(23)
The anisotropic area and perimeter generating function and partial generating functions , connected by
(24)
satisfy the self-reciprocity and inversion relations
(25)
and
(26)
(Bousquet-Mélou et al. 1999).
See alsoColumn-Convex Polyomino,
Directed Convex Polyomino,
Parallelogram Polyomino,
Polyomino,
Stack Polyomino,
Staircase Polygon Explore with Wolfram|Alpha ReferencesBender, E. "Convex -ominoes." Disc. Math. 8, 31-40, 1974.Bousquet-Mélou, M. "Convex Polyominoes and Heaps of Segments." J. Phys. A: Math. Gen. 25, 1925-1934, 1992a.Bousquet-Mélou, M. "Convex Polyominoes and Algebraic Languages." J. Phys. A: Math. Gen. 25, 1935-1944, 1992b.Bousquet-Mélou, M. "A Method for Enumeration of Various Classes of Column-Convex Polygons." Disc. Math. 154, 1-25, 1996.Bousquet-Mélou, M.; Guttmann, A. J.; Orrick, W. P.; and Rechnitzer, A. "Inversion Relations, Reciprocity and Polyominoes." 23 Aug 1999. http://arxiv.org/abs/math.CO/9908123.Delest, M.-P. and Viennot, G. "Algebraic Languages and Polyominoes [sic] Enumeration." Theoret. Comput. Sci. 34, 169-206, 1984.Gessel, I. M. "On the Number of Convex Polyominoes." Ann. des Sci. Math. du Quebec, 24, 63-66, 2000.Guttmann, A. J. and Enting, I. G. "The Number of Convex Polygons on the Square and Honeycomb Lattices." J. Phys. A 21, L467-L474, 1988.Klarner, D. and Rivest, R. "Asymptotic Bounds for the Number of Convex -ominoes." Disc. Math. 8, 31-40, 1974.Lin, K. Y. and Chang, S. J. "Rigorous Results for the Number of Convex Polygons on the Square and Honeycomb Lattices." J. Phys. A: Math. Gen. 21, 2635-2642, 1988.Sloane, N. J. A. Sequence A005436/M1778 in "The On-Line Encyclopedia of Integer Sequences."Temperley, H. N. V. "Combinatorial Problems Suggested by the Statistical Mechanics of Domains and of Rubber-Like Molecules." Phys. Rev. 103, 1-16, 1956. Referenced on Wolfram|AlphaConvex Polyomino Cite this as:Weisstein, Eric W. "Convex Polyomino." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/ConvexPolyomino.html
Subject classificationsRetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4