TOPICS
Search

Convex Polyomino

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook
ConvexPolyominoes

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 a_n of convex polyominoes having area n as

a_n∼cgamma^n,
(1)

with gamma=2.30914... and c=2.67564... (Delest and Viennot 1984).

The anisotropic perimeter and area generating function

G(x,y,q)=sum_(m>=1)sum_(n>=1)sum_(a>=1)C(m,n,a)x^my^nq^a,
(2)

where C(m,n,a) is the number of polygons with 2m horizonal bonds, 2n vertical bonds, and area a is given by

G(x,y,q)=2sum_(m>=1)(y^(m+2))/((xq)_m^2N(xq^(m-1))N(xq^m))[T_(m+1)S(xq^m)-yT_mS(xq^(m+1))]^2+sum_(m>=1)(xy^mq^m(T_m)^2)/((xq)_(m-1)(xq)_m),
(3)

where

N(x)=sum_(n>=0)((-1)^nx^nq^((n+1; 2)))/((q)_n(yq)_n)
(4)
S(x)=sum_(n>=1)[(x^nq^n)/((yq)_n)sum_(j=0)^(n-1)((-1)^jq^((j; 2)))/((q)_j(yq^(j+1))_(n-j))]
(5)

and T_n(x) is the polynomial recurrence relation

T_n(x)=2T_(n-1)(x)+(xq^(n-1)-1)T_(n-2)(x)
(6)

with T_0(x)=1 and T_1(x)=1 (Bousquet-Mélou 1992b). The first few of these polynomials are given by

T_2(x)=1+qx
(7)
T_3(x)=1+(2q+q^2)x
(8)
T_4(x)=1+(3q+2q^2+q^3)x+q^4x^2
(9)
T_5(x)=1+(4q+3q^2+2q^3+q^4)x+(2q^4+2q^5+q^6)x^2.
(10)

Expanding the generating function shows that the number of convex polyominoes having perimeter 2n+8 is given by

p_(2n+8)=(2n+11)4^n-4(2n+1)(2n; n),
(11)

where p_4=1, p_6=2, and (n; k) is a binomial coefficient (Delest and Viennot 1984, Bousquet-Mélou 1992ab). The generating function for p_(2n) is explicitly given by

sum_(n=2)^inftyp_(2n)t^(2n)=(t^4(1-6t^2+11t^4-4t^6))/((1-4t^2)^2)-4t^8(1-4t^2)^(-3/2)
(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). G(1,1,q) is a q-series, but becomes algebraic for column-convex polyominoes. However, G(x,y,q) for column-convex polyominoes again involves q-series (Temperley 1956, Bousquet-Mélou et al. 1999).

G(x,y)=G(x,y,1) is an algebraic function of x and y (called the "fugacities") given by

G(x,y)=sum_(x>=1)sum_(y>=1)C(m,n)x^my^n
(13)
=(R(x,y)xy)/([Delta(x,y)]^2)-(4x^2y^2)/(Delta^(3/2)),
(14)

where

R(x,y)=1-3x-3y+3x^2+3y^2+5xy-x^3-y^3-x^2y-xy^2-xy(x-y)^2
(15)
Delta(x,y)=1-2x-2y-2xy+x^2+y^2
(16)
=(1-y)^2[1-(x(2+2y-x))/((1-y)^2)]
(17)

(Lin and Chang 1988, Bousquet-Mélou 1992ab). This can be solved to explicitly give

C(m,n)=(mn-1)/(m+n-2)(2m+2n-4; 2m-2) -2(m+n-2)(m+n-3; m-1)(m+n-3; n-1)
(18)

(Gessel 2000, Bousquet-Mélou 1992ab).

G(x,y) satisfies the inversion relation

G(x,y)+y^3G(x/y,1/y)=xy-x^3ypartial/(partialx)(1-x+y)/(Delta(x,y)),
(19)

where

Delta(x,y)=1-2x-2y-2xy+x^2+y^2
(20)
=(1-y)^2[1-(x(2+2y-x))/((1-y)^2)]
(21)

(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

H_3(y,q)=(yq^3)/((1-yq)^4(1-yq^2)^2(1-yq^3))(y^6q^8+4y^5q^7+2y^5q^6+y^4q^6-y^4q^4-4y^3q^5-6y^3q^4-4y^3q^3-y^2q^4+y^2q^2+2yq^2+4yq+1)
(22)

of the general rational function (Bousquet-Mélou et al. 1999), which satisfies the reciprocity relation

H_3(1/y,1/q)=-1/(yq^3)H_3(y,q).
(23)

The anisotropic area and perimeter generating function G(x,y,q) and partial generating functions H_m(y,q), connected by

G(x,y,q)=sum_(m>=1)H_m(y,q)x^m,
(24)

satisfy the self-reciprocity and inversion relations

H_m(1/y,1/q)=-1/(yq^m)H_m(y,q)
(25)

and

G(x,y,q)+yG(xq,1/y,1/q)=0
(26)

(Bousquet-Mélou et al. 1999).

See also

Column-Convex Polyomino, Directed Convex Polyomino, Parallelogram Polyomino, Polyomino, Stack Polyomino, Staircase Polygon

Explore with Wolfram|Alpha

References

Bender, E. "Convex n-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 n-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|Alpha

Convex Polyomino

Cite this as:

Weisstein, Eric W. "Convex Polyomino." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/ConvexPolyomino.html

Subject classifications