A convex polyomino (sometimes called a "convex polygon") is a polyomino that is both a row-convex polyomino and a column-convex polyomino. Equivalently, its perimeter equals that of its minimal bounding box (Bousquet-Mélou et al. 1999). If it furthermore contains at least one corner of its minimal bounding box, it is said to be a directed convex polyomino. A number of types of named convex polyominoes are depicted above (Bousquet-Mélou et al. 1999). Polyominoes are counted up to translation, with rotations and reflections distinguished.
Bender (1974) gave the asymptotic estimate for the number of convex polyominoes having area
as
|
(1)
|
with
and
. Klarner and Rivest (1974) determined
the growth constant
.
The anisotropic perimeter and area generating function
|
(2)
|
where
counts convex polyominoes with
horizontal boundary edges,
vertical boundary edges, and area
, is given by
|
(3)
|
where
|
(4)
| |||
|
(5)
|
and
is the polynomial defined by the recurrence
relation
|
(6)
|
for , with
and
(Bousquet-Mélou 1992b). The first few of these
polynomials are given by
|
(7)
| |||
|
(8)
| |||
|
(9)
| |||
|
(10)
|
Expanding the generating function shows that the number of convex polyominoes having perimeter is given by
|
(11)
|
for nonnegative integers , 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 counts for
, 3, ... are 1, 2, 7, 28, 120,
528, 2344, 10416, ... (OEIS A005436).
Corresponding joint area and perimeter generating functions are also known for column-convex
polyominoes and directed column-convex
polyominoes (Bousquet-Mélou 1996, Bousquet-Mélou et al. 1999).
The area generating function is a q-series.
For column-convex polyominoes, both the
area generating function
and the anisotropic perimeter generating
function are algebraic functions, while
the joint area and perimeter generating function involves q-series
(Temperley 1956, Bousquet-Mélou 1996, Bousquet-Mélou et al. 1999).
is an algebraic
function of
and
(called the "fugacities") given by
|
(13)
| |||
|
(14)
|
where
|
(15)
| |||
|
(16)
| |||
|
(17)
|
(Lin and Chang 1988, Bousquet-Mélou 1992ab), where counts convex polyominoes whose minimal bounding box
has
columns and
rows. The coefficients are explicitly given by
|
(18)
|
for positive integers and
with
, together with
(Bousquet-Mélou 1992ab; Gessel 2000, pp. 63-65).
satisfies the inversion relation
|
(19)
|
where
|
(20)
| |||
|
(21)
|
(Lin and Chang 1988, Bousquet-Mélou et al. 1999).
The half-vertical perimeter and area generating function for column-convex polyominoes 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 for column-convex
polyominoes, denoted by , and its width-
partial generating
functions
, connected by
|
(24)
|
satisfy the self-reciprocity and inversion relations
|
(25)
|
and
|
(26)
|
(Bousquet-Mélou et al. 1999).