We show that, for any fixed integer > 2, the problem of computing the number of -convex polyominoes of area is in P. A polyomino is a geometrical figure consisting of a finite set of connected unit squares (called cells) in the plane Z × Z, considered up to translations. Polyominoes gained popularity after the paper of S. W. Golomb [1]. Nowadays they are widely studied by physicists, mathematicians, computer scientists and also by biologists. The problem of counting the number of polyominoes with cells (i.e. of area ) is probably one of the fundamental open problems in combinatorial geometry (see problem 37 in [2]). Due to the dificulty of the problem, simpler classes of polyominoes have been introduced. In particular, the class of convex polyominoes (polyominoes where the intersection with an infinite horizontal or vertical stripe is a finite segment) and some of its subclasses have been investigated [3, 4, 5, 6, 7]. In this paper, we consider the class Conv [8] containing all convex polyominoes with the property that any two cells of can be joined by a path in with at most changes of direction, where is a ifxed integer greater than 2. We show that, for any fixed > 2, the algorithm presented in [9] leads to a set of recurrence equations for computing the number of -convex polyominoes of area in polynomial time, using (5) space. Let be a polyomino with an × minimal bounding rectangle. The rows (resp., columns) of are numbered from bottom to top (resp., from left to right). The area A( ) of is the number of its cells. A cell of is identified by a pair of integers (, ), where (resp., ) is the row (resp., column) index. Two cells = (, ) and ′ = (′, ′) are adjacent if | − ′| + | − ′| = 1. Given two cells and of , a path in from to is a sequence 1, 2, . . . , of cells of , with 1 = and = , such that and +1 are adjacent for all with 1 ≤ < . A
step is a sequence of two adjacent cells (, ), (′, ′). Steps are distinguished according to the
directions N (North), W (West), S (South) and E (East). The number of changes of direction
in a path ∈ {N, W, S, E}+ is defined as the number of indices such that ̸= +1, with
1 ≤ < | |. A path is monotone if ∈ {N, W}+ (NW-path) or ∈ {N, E}+ (NE-path) or
∈ {S, E}+ (SE-path) or ∈ {S, W}+ (SW-path). A polyomino is horizontally convex (resp.,
vertically convex) if any row (resp. column) of consists of one segment. The class of convex
polyominoes contains all polyominoes that are both horizontally and vertically convex. It has
been proved [10, Proposition 1] that a polyomino is convex if and only if any two cells of
are joined by a monotone path in . The degree of convexity of , denoted by deg( ),
is defined as the least integer such that any two cells of can be joined by a monotone
path in with at most changes of direction. A convex polyomino is called -convex if its
degree of convexity is at most . Given a convex polyomino and its minimal bounding
rectangle , we say that is a stack (resp., Ferrers diagram, parallelogram, rectangle) if it shares
exactly two adjacent (resp., three, two opposite, four) vertices with . A stack is a left (resp.,
right) stack if the column with the largest area is the last (resp., first) one. Analogously, in a
left (resp., right) Ferrers diagram the largest column is the last (resp., first) one. We denote
by L (resp., R) the set of left (resp., right) stacks. F (resp., F) is the set of left (resp., right)
Ferrers diagrams. Furthermore, we indicate by C (resp., T) the set of parallelograms (resp.,
rectangles). For a class A of polyominoes, A() is the set of polyominoes in A of area . By
low() (resp., high()) we denote the row index of the bottom (resp., top) cell of column .
Similarly, left() denotes the column index of the leftmost cell of row . Lastly, first( )
(resp., last( )) indicates the first (resp., last) column of . Given two columns and , we
say that and are overlapping (resp., disjoint), denoted by ⇄ (resp., ≍ ), if and only if
low() < low() ≤ high() < high() or low() < low() ≤ high() < high() (resp.,
low() > high() or low() > high()). Moreover, we say that includes , denoted by ⊆ ,
if and only if low() ≤ low() and high() ≥ high(). Given a convex polyomino , let
be the rightmost column of such that ⊆ for 1 ≤ < . Then, is called descending
(resp., ascending) if there exists a column such that > , ⇄ and low() > low() (resp.,
low() < low()). The set of descending (resp., ascending) -convex polyominoes is indicated
by DConv (resp., AConv). The set of all descening polyominoes is DConv. If is neither
descending nor ascending then ∈ T ∪ F ∪ F ∪ L ∪ R or it belongs to the class LR containing
all convex polyominoes that are the concatenation of two polyominoes, = 1 · 2, where
1 ∈ L ∪ F, 2 ∈ T ∪ R ∪ F and first(2) ⊊ last(1). Notice that any ∈ LR contains
a column ¯ such that ⊆ ¯ for all columns , hence deg( ) ≤ 2. Lastly, a cell (, ) of is
a NW-corner if (, − 1) and ( + 1, ) are not cells of . Analogously, we define NE-corners,
SE-corners and SW-corners. Two corners are called opposite if either one is a NW-corner and
the other is a SE-corner, or one is a NE-corner and the other is a SW-corner. Clearly, one
has Conv = T ∪ F ∪ F ∪ L ∪ R ∪ LR ∪ AConv ∪ DConv and (because of symmetry)
|DConv()| = |AConv()|, |L()| = |R()|, |F()| = |F()|. Since all unions are disjoint,
it follows that
|Conv()| = |T()| + 2 · | F()| + 2 · | L()| + |LR()| + 2 · | DConv()|.
(
Definition 2.1 (standard decomposition). A polyomino ∈ DConv can be decomposed as = · · · (with , possibly empty) for suitable polyominoes ∈ L ∪ T ∪ F, ∈ F, ∈ C ∪ T ∪ F, and ∈ R ∪ T ∪ F such that: first( ) ⊊ last(), low(last()) = low(first( )), last( ) ⇄first() (or last() ⇄first() if = ), low(last()) > low(first()) and (if ̸= ) first() ⊊ last(), low(last()) < low(first()).
We stress that the standard decomposition of is unique (e.g. last() is the rightmost column ¯ of such that ⊆ ¯ for < ¯). The subset of DConv2 containing polyominoes decomposed as · · (resp., · , · · · , · · ) is LCR2 (resp., LC2, LFCR2, LFC2). Thus, for any > 2 one has the partition DConv = LFCR ∪ LFC ∪ LCR ∪ LC.
By [9, Thm. 6], the degree of convexity of ∈ DConv depends on the number of changes of direction in a particular NW-path that starts at a SE-corner and ends at a NW-corner . This is a path where the first − 1 changes of direction always occur on the boundary of , whereas the th one possibly occurs on a cell that is not on the boundary. Furthermore, from [9, Thm. 6] it follows that the degree of convexity of the th column of is deg(, ) = max{(, )| = (low() , ), is a NW-corner of }, where (, ), is the least integer k such that there exists a monotone path in from to with k changes of direction.
Given = · · · and a column in · · , we know from [9, Lemma 8] that deg(, ) = min(deg(, ′) + 2, deg(, ′′) + 1), where ′ = left(high()) and ′′ = left(low()). see Fig. 1 for an example. In the sequel, we consider each column of as the concatenation of vertical segments associated with diferent degrees of convexity. These segments are identified by considering the degrees of convexity of the leftmost columns that are reached by W-paths starting from cells of .
Definition 2.2 ( -segment). A cell (, ) of ∈ DConv belongs to a -segment if and only if either > 0 ∧ < low(first( )) and the cell (, left()) belongs to a column of degree of convexity , or = 0 ∧ ≥ low(first( )).
From [9, Lemma 8], if deg(, ) = then column may contain only -segments with − 2 ≤ ≤ . Notice that (, ) belongs to a -segment if and only if (, − 1) belongs to a -segment or (, − 1) is not in and deg(, ) = . Fig. 1 shows how the columns of a polyomino in DConv consist of at most three -segments (depicted as vertical segments comprising cells of the same color).
We focus on computing |DConv()| since the remaining values in (
Consider the standard decomposition of a polyomino counted by (, , , , , ), =
· · or = · . If the second to last column of belongs to then (, , , , , )
depends on ( − , ′, ′, ′, ′, ′) for suitable ′, ′, ′, ′, ′. Otherwise, the second to last
column of is in or in , and (, , , , , ) is computed using the values (′, ′, ′, ′)
and (′, ′, ′), where (′, ′, ′, ′) (resp., (′, ′, ′)) is the number of ∈ L(′) ∪
F(′) ∪ T(′) (resp. ∈ F(′)) such that A(first( )) = ′, A(last( )) = ′ and
low(first( ))− low(last( )) = ′. Here we consider only the case when column last( )−
1 is in (we refer to the full paper for the remaining cases). This is the most complex case
as it leads to four diferent equations, depending on the conditions > (
• the area ′ of column last( ) − 1 is at least − + 1 (since ′ must contain a ( − 3)segment) and at most − − 2 (since A() ≥ 2); • the area ′ of the ( − 2)-segment in last( ) − 1 is at least − − (the area of the ( − 2)-segment in last( )) and at most ′ − + − 1 (because column last( ) − 1 must contain a ( − 3)-segment); • ′ is at least 0 and at most (the lower ′ cells of last( ) − 1 has degree − 1 since left(low(last( ) − 1) + ) = last( ) − 1 for 0 ≤ < ′).
Otherwise, if deg(, last( ) − 1) = we sum the values ( − , ′, , 0, , 0) on all ′ no
smaller than − and no greater than − − 2. From the existence of a ( − 1)-segment in
last( ) and deg(, last( )− 1) = , it follows low(last( ) − 2)− low(last( ) − 1) = 0.
Hence, last( ) − 1 cannot contain a -segment. The recurrence equations for cases (
Based on these equations, we have developed a C++ program to compute |Conv()| for > 2 and > 0. This program has space complexity (5) (coming from the size of the table containing the values (, , , , , )) and produced Table 1 in few minutes (on a Macbook Pro). We point out that this integer sequence does not appear in OEIS.
0, 1, 2, 6, 19, 59, 172, 470, 1206, 2934, 6812, 15192, 32709, 68282, 138678, 274822, 532719, 1012144 1888226, 3464168, 6258249, 11146013, 19590450, 34011064, 58371083, 99103808, 166563604, 277281796, 457451501, 748274488, 1214117566, 1954879052, 3124637754, 4959621329, 7819943680, 12251575214, 19077932142, 29534613958, 45466767846, 69616951878, 106043316448