=Paper=
{{Paper
|id=Vol-3072/paper16
|storemode=property
|title=On Counting L-Convex Polyominoes
|pdfUrl=https://ceur-ws.org/Vol-3072/paper16.pdf
|volume=Vol-3072
|authors=Valentina Dorigatti,Paolo Masazza
|dblpUrl=https://dblp.org/rec/conf/ictcs/DorigattiM21
}}
==On Counting L-Convex Polyominoes==
https://ceur-ws.org/Vol-3072/paper16.pdf
On Counting L-Convex Polyominoes (short
paper)?
Valentina Dorigatti1 and Paolo Massazza1
Department of Theoretical and Applied Sciences
University of Insubria, Varese, Italy
{vdorigatti,paolo.massazza}@uninsubria.it
Abstract. A convex polyomino P is L-convex if any two cells of P
can be joined by a monotone path inside P with at most one change
of direction. In this paper we show that the problem of computing the
number of L-convex polyominoes of area n can be solved in polynomial
time using O(n4 ) space. We designed a C++ program to significantly
extend the counting sequence of L-convex polyominoes and to improve
the estimate of the associated growth constant.
Keywords: convex polyominoes · counting problem · integer sequences
1 Introduction
A polyomino is a geometrical figure consisting of a finite set of connected unitary
squares (called cells) in the plane Z × Z, considered up to translations. Polyomi-
noes gained popularity after the paper of S. Golomb [8]. They are widely studied
by physicists, mathematicians, computer scientists and biologists.
The problem of counting the number of polyominoes with n cells (i.e. of
area n) is probably one of the fundamental open problems in combinatorial
geometry, see problem 37 in [1]. The problem has been solved up to n ≤ 56 [9]
and no closed-form expression is known for the general case. Due to the difficulty
of the problem, suitable classes of polyominoes have been introduced and widely
studied. In particular, the class of hv-convex polyominoes (polyominoes where
the intersection with an infinite horizontal or vertical stripe is a finite segment)
and some of its subclasses have been deeply investigated [2,3,11,6].
In this paper we deal with the problem of computing the coefficient cn of the
generating function (with respect to the area) of the class LConv of L-convex
polyominoes. This class has been introduced in [5] as the first level in the hierar-
chy of hv-convex polyominoes, and studied in the context of discrete tomography
in [7], where it has been shown that an L-convex polyomino is uniquely deter-
mined by two integer vectors representing its vertical and horizontal projections.
Lastly, in [4] a non-closed form expression for the generating function (with re-
spect to the area) of LConv has been provided.
?
Copyright c 2021 for this paper by its authors. Use permitted under Creative Com-
mons License Attribution 4.0 International (CC BY 4.0).
2 V. Dorigatti, P. Massazza
We show a simple decomposition of L-convex polyominoes that is used to
obtain a set of recurrence equations for computing the number of L-convex
polyominoes of area n in polynomial time and O(n4 ) space. Indeed, we designed
a C++ program that uses dynamic programming to extend sequence A126764
in OEIS from n < 19 up to n ≤ 120, so obtaining a better estimate of the growth
constant of LConv, λ = 1.2207.
2 Notation and preliminaries
Let P be a polyomino with a r×c minimal bounding rectangle. The r rows (resp.,
c columns) of P are numbered from bottom to top (resp., from left to right).
The area of P is the number of its cells, denoted by A(P ). A cell is identified by
a pair of integers (i, j), where i (resp., j) is the row (resp., column) index. Two
cells a = (i, j) and a0 = (i0 , j 0 ) are adjacent if |i − i0 | + |j − j 0 | = 1. Given two
cells a and b of P , a path from a to b is a sequence q1 , . . . , qk of cells of P , with
q1 = a and qk = b, such that qi and qi+1 are adjacent for all i, with 1 ≤ i < k.
A step is a sequence of two adjacent cells (i, j), (i0 , j 0 ), and it’s called North step
(resp. South step) if i0 = i + 1 (resp., i0 = i − 1) and j 0 = j. Similarly, for a West
step (resp. East step) one has j 0 = j − 1 (resp., j 0 = i + 1) and i0 = i.
A path of lenght r in P is uniquely identified by indicating a starting cell and
a string β ∈ {N, W, S, E}r . The number of changes of direction in β = β1 β2 . . . βr
is defined as the number of indices i such that βi 6= βi+1 , with 1 ≤ i < r. A
path is monotone if β ∈ {N, W}+ ∪ {N, E}+ ∪ {S, E}+ ∪ {S, W}+ (the symbol ’+’
denotes the positive closure).
A polyomino P belongs to the class Conv of hv-convex (convex, for short)
polyominoes if any column and any row of P is a segment (a sequence of adjacent
cells). It has been proved [5, Proposition 1] that P is convex if and only if any
two cells of P are joined by a monotone path in P . Monotone paths allow to
define the zigzag-distance between two cells a, b of P , denoted by D(a, b), as the
least integer k such that there exists a monotone path from a to b with k changes
of direction (we use the term distance in an informal way, since P equipped with
D is not a metric space).
From here on we consider only convex polyominoes. The degree of convexity
of P , denoted by Dc (P ), is the least integer k such that any two cells of P
can be joined by a monotone path with at most k changes of direction, that
is, Dc (P ) = max{D(a, b) : a, b ∈ P }. Furthermore, P is called k-convex if its
degree of convexity is at most k. When k = 1 we have the class LConv of L-
convex polyominoes introduced in [5]. We denote by LConv(n) the subset of
LConv containing polyominoes of area n.
A polyomino P is a stack (resp., Ferrers diagram) if it shares exactly two
(resp, three) adjacent vertices with its smallest bounding rectangle B. The height
of a stack P , denoted by height(P ), is the area of its largest column. A stack P is
a left (resp., right) stack if the area of its last (resp., first) column is height(P ).
We denote by L (resp., R) the set of left (resp., right) stacks, whereas F stands
for the class of Ferrers diagrams.
On Counting L-Convex Polyominoes 3
Fig. 1. From left to right: a polyomino in LR1 (no disjoint or overlapping columns), a
polyomino in LR2 (no disjont columns, at least one column includes any other column),
a descending polyomino and an ascending polyomino.
By low(j) (resp., high(j)) we indicate the row index of the bottom cell
(resp., top cell) of column j of P . Furthermore, by first(P ) (resp., last(P ))
we indicate the first (resp., last) column of P .
Given two columns i, j, we say that: i includes j, denoted by j ⊆ i, if and
only if low(i) ≤ low(j) and high(i) ≥ high(j); i and j are overlapping if
and only if low(j) < low(i) ≤ high(j) < high(i) or low(i) < low(j) ≤
high(i) < high(j); i and j are disjoint if and only if low(i) > high(j) or
low(j) > high(i). If neither i ⊆ j nor j ⊆ i then i and j are disjoint or
overlapping.
A convex polyomino P is called descending (resp., ascending) if it contains
two overlapping columns j1 and j2 such that j1 < j2 and low(j2 ) < low(j1 )
(resp., low(j2 ) > low(j1 )), and there is not a column ̄ of P such that j ⊆ ̄
for all columns j of P , see Fig. 1 (iii) and (iv). If P is neither descending nor
ascending then P is uniquely decomposed as concatenation of two polyomi-
noes, P = P1 · P2 , where the last column of P1 includes any column of P , with
first(P2 ) ( last(P1 ), see Fig. 1 (i) and (ii). Notice that P1 (resp., P2 ) is a
rectagle or belongs to ∈ L ∪ F (resp., P2 ∈ R ∪ F). We denote by LR the class of
these polyominoes. Notice that LR includes both R and L and F.
The degree of convexity of P ∈ LR is at most 2 as P contains a column ̄ such
that j ⊆ ̄ for all columns j of P . Analogously, if P is descending or ascending
then D(P ) ≥ 2 since P contains two overlapping columns j1 , j2 and D(a, b) = 2,
where a (resp., b) is the top (resp., bottom) cell of j1 (resp., j2 ).
As a matter of fact, LConv is a subset of LR. So, we consider the partition
LR = LR1 ∪ LR2 , where LRi = {P ∈ LR : Dc (P ) = i}. In other words, one has
LConv = LR1 . The following property is the basis of the decomposition used to
obtain a formula for |LConv(n)| = |LR1 (n)|.
Property 1. A convex polyomino P is in LR1 if and only if for any two columns
i and j of P one has i ⊆ j or j ⊆ i.
Proof. If P is in LR and contains two columns that are disjoint or overlapping
then Dc (P ) = 2, that is P ∈ LR2 .
4 V. Dorigatti, P. Massazza
3 Polyominoes decomposition and counting
In this section we provide a decomposition for P ∈ LR1 (n) that is useful to
obtain a set of recurrence equations for computing |LR1 (n)|. We consider the
partition [
LR1 (n) = LR1 (n, p, q, i),
p,q,i
where LR1 (n, p, q, i) is the set of all P ∈ LR1 (n) such that p = A(first(P )),
q = A(last(P )) and i = |low(first(P )) − low(last(P )) |. Without loss of
generality, in the following we suppose that p ≥ q. Indeed, by symmetry one has
|LR1 (n, p, q, i)| = |LR1 (n, q, p, i)|.
Consider a polyomino P ∈ LR1 (n, p, q, i). If P does not contain a column
of area larger than p then P belongs to the set R(n, p, q, i) comprising all poly-
ominoes of area n that are rectangles or belong to R ∪ F, and such that p =
height(P ), q = A(last(P )) and i = low(last(P )) − low(first(P )). Oth-
erwise, consider the rightmost column in P with area r > p and write P as
concatenation of two polyominoes, P = P 0 · R0 , with P 0 ∈ LR1 (n − z, p, r, j)
and R0 ∈ R(z, e, q, k), where e, z, k, j ∈ N are uniquely identified (q ≤ e ≤ p,
q ≤ z ≤ n − p − r), see Fig. 2.
By considering the decomposition P = P 0 · R0 , we get the following partition:
[
LR1 (n, p, q, i) = R(n, p, q, i) ∪ LR1 (n − z, p, r, j) · R(z, e, q, k), (1)
r,j,z,e,k
where the union is taken over all values r, j, z, e, k such that:
– p < r ≤ n − p − q (remark: A(first(P 0 )) = p and A(last(R0 )) = q);
– 0 ≤ j ≤ r − p (j = r − p if high(first(P 0 )) = high(last(P 0 )), whereas
j = 0 if low(first(P 0 )) = low(last(P 0 )));
– q ≤ z ≤ n − p − r (remark: A(P 0 ) ≥ p + r, R0 contains at least one column
of area q);
– 0 ≤ k ≤ i (due to convexity);
– q + k ≤ e ≤ k + p − i (remark: first(R0 ) ⊆ first(P 0 )).
We refer to Fig. 2 for a better understanding of the conditions on r, j, z, e, k. It
is immediate that in (1) all unions (resp. products) are disjoint (resp. unambigu-
ous). In particular, given P 0 ∈ LR1 (n − z, p, r, j) and R0 ∈ R(z, e, q, k) there is
only one way of obtaining a polyomino in LR1 (n, p, q, i): concatenate R0 to P 0 so
that low(first(R0 )) − low(last(P 0 )) = i − k + j.
Since the set R(z, e, q, k) appears in (1) we consider also the decomposition
[
R(n, p, q, i) = R(p, p, p, 0) · R(n − p, r, q, j) (2)
q+j≤r≤p−i+j
0≤j≤i
Indeed, R ∈ R(n, p, q, i) is the concatenation of a one-column rectangle R0 ∈
R(p, p, p, 0) and a polyomino R00 ∈ R(n − p, r, q, j) for suitable r and j. Notice
On Counting L-Convex Polyominoes 5
Fig. 2. Decomposition of a polyomino P ∈ LR1 (n). R0 has area z, while P 0 has area
n − z.
Fig. 3. Decomposition of a polyomino in R. Considering n as the total area, the stack
R0 has area p (since it includes only column p), while the stack R00 has area n − p.
that the position of R00 with respect to R0 is uniquely determined by i and j,
since i − j = |low(first(R00 )) − low(first(R0 )) |, see Fig. 3.
The recurrence equations used to compute |LConv(n)| follow directly from
the above decompositions.
4 Conclusions
By applying dynamic programming it is straightforward to develop a program
that uses tables of size O(n4 ) to store the cardinalities of the sets R(n, p, q, i)
and LR(n, p, q, i). Since each entry in a table is computed in polynomial time,
we conclude that there exists a polynomial algorithm to compute |LConv(n)|.
We developed a C++ program that computes |LConv(n)| for large n. The source
code is available at:
https://sites.google.com/view/polyominoesgeneration/home
Table 1 shows the first 121 values of the sequence {|LConv(n)|}n≥0 , (previ-
ously computed [4] only for n < 19 - sequence A126764 in OEIS). The sequence
has been computed in 20 minutes on an entry-level laptop.
The knowledge of more values of the counting sequence for LConv is of great
importance since it allow to obtain a better approximation of the growth constant
λ of the class LConv. Indeed, we recall that for any class of polyominoes with
1/n
counting sequence {cn } it holds limn7→∞ cn = λ [10]. In particular, if a class
of polyominoes satisfies Axioms Ca1–Ca5 in [12] one has the stronger result
6 V. Dorigatti, P. Massazza
Table 1. |LConv(n)| for 0 ≤ n ≤ 120.
1, 1, 2, 6, 15, 35, 76, 156, 310, 590, 1098, 1984, 3515, 6094, 10398, 17434, 28837, 47038, 75820, 120794,
190479, 297365, 460056, 705576, 1073473, 1620680, 2429352, 3616580, 5349359, 7863564, 11491946, 16700534,
24140606, 34716813, 49682700, 70766326, 100343410, 141665826, 199172140, 278897192, 389023478, 540606678,
748543820, 1032844616, 1420315158, 1946761600, 2659891076, 3623095094, 4920401713, 6662912574, 8997185064,
12116088688, 16272878335, 21799355950, 29129313088, 38828680480, 51634288623, 68503548132, 90678083896,
119765026500, 157840769584, 207583098066, 272439268276, 356839386632, 466466992155, 608601537859,
792551372020, 1030200202402, 1336695959993, 1731317801706, 2238566012418, 2889530083444, 3723603926469,
4790633313200, 6153601295172, 7891981954408, 10105923985926, 12921462874542, 16497007238584,
21031401126748, 26773934116473, 34036755475474, 43210253221164, 54782085062392, 69360703770136,
87704407338787, 110757174873692, 139692827677312, 175969395713746, 221395981085892, 278214911971700,
349202586196148, 437793140235291, 548229968120604, 685751192735588, 856816491322044, 1069384249807199,
1333249914358312, 1660458696133736, 2065808536877134, 2567462560505766, 3187694221776132,
3953793160381426, 4899165525940288, 6064669456588960, 7500234685505662, 9266825196490576,
11438815758244096, 14106867431540154, 17381404200712580, 21396813283137772, 26316516037970698,
32339085501320858, 39705621296067648, 48708634082324850, 59702741064184742, 73117532860023593,
89473042013023344, 109398326670950676, 133653781930341812, 163157908951796052
limn7→∞ cn+1
cn = λ. In our case, this means a significant improvement of the
estimate of λ, from cc17
18
= 1.6118 . . . to cc120
119
= 1.2207.
We plan to extend the approach here presented to obtain suitable recurrences
for computing the number of k-convex polyominoes of given area in polynomial
time, for any k > 1.
References
1. The open problems project, https://topp.openproblem.net/.
2. M. Bousquet-Melou. Convex polyominoes and heaps of segments. Journal of
Physics A: Mathematical and General, 25(7):1925–1934, apr 1992.
3. M. Bousquet-Mélou. A method for the enumeration of various classes of column-
convex polygons. Discrete Math., 154(1-3):1–25, 1996.
4. G. Castiglione, A. Frosini, E. Munarini, A. Restivo, and S. Rinaldi. Combinatorial
aspects of l-convex polyominoes. Eur. J. Comb., 28(6):1724–1741, 2007.
5. G. Castiglione and A. Restivo. Reconstruction of l-convex polyominoes. Electronic
Notes in Discrete Mathematics, 12:290–301, 2003. 9th International Workshop on
Combinatorial Image Analysis.
6. G. Castiglione and A. Restivo. Ordering and convex polyominoes. In MCU 2004,
volume 3354 of Lecture Notes in Comput. Sci., pages 128–139. Springer, 2005.
7. Giusi Castiglione, Andrea Frosini, Antonio Restivo, and Simone Rinaldi. A tomo-
graphical characterization of L-convex polyominoes. In DGCI05, volume 3429 of
Lecture Notes in Comput. Sci., pages 115–125. Springer, 2005.
8. S. W. Golomb. Checker boards and polyominoes. Amer. Math. Monthly, 61:675–
682, 1954.
9. Iwan Jensen. Counting polyominoes: A parallel implementation for cluster com-
puting. In Proceedings of the 2003 International Conference on Computational
Science: Part III, ICCS’03, pages 203–212. Springer-Verlag, 2003.
10. David A. Klarner. Cell growth problems. Canadian Journal of Mathematics,
19:851–863, 1967.
11. A. Del Lungo, M. Nivat, R. Pinzani, and S. Rinaldi. A bijection for the total area
of parallelogram polyominoes. Discret. Appl. Math., 144(3):291–302, 2004.
12. Neal Madras. A pattern theorem for lattice clusters. Annals of Combinatorics,
3(3):357–384, 1999.