Convex Polyomino


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). Furthermore, if it 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.

Klarner and Rivest (1974) and Bender (1974) gave the asymptotic estimate for the number a_n of convex polyominoes having area n as


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

The anisotropic perimeter and area generating function


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



N(x)=sum_(n>=0)((-1)^nx^nq^((n+1; 2)))/((q)_n(yq)_n)
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))]

and T_n(x) is the polynomial recurrence relation


with T_0(x)=1 and T_1(x)=1 (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 2n+8 is given by

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

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


(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




(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)

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

G(x,y) satisfies the inversion relation




(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


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


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


satisfy the self-reciprocity and inversion relations




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

See also

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

Explore with Wolfram|Alpha


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., 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.

Subject classifications