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 signi cantly extend the counting sequence of L-convex polyominoes and to improve the estimate of the associated growth constant.
A polyomino is a geometrical gure consisting of a nite set of connected unitary squares (called cells) in the plane Z Z, considered up to translations. Polyominoes 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 di culty 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 in nite horizontal or vertical stripe is a nite 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 coe cient 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 rst level in the hierarchy 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 determined by two integer vectors representing its vertical and horizontal projections. Lastly, in [4] a non-closed form expression for the generating function (with respect to the area) of LConv has been provided. ? Copyright c 2021 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
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
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 identi ed 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; j0) are adjacent if ji i0j + jj j0j = 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; j0), and it's called North step (resp. South step) if i0 = i + 1 (resp., i0 = i 1) and j0 = j. Similarly, for a West step (resp. East step) one has j0 = j 1 (resp., j0 = i + 1) and i0 = i.
A path of lenght r in P is uniquely identi ed by indicating a starting cell and a string 2 fN; W; S; Egr. The number of changes of direction in = 1 2 : : : r is de ned as the number of indices i such that i 6= i+1, with 1 i < r. A path is monotone if 2 fN; Wg+ [ fN; Eg+ [ fS; Eg+ [ fS; Wg+ (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 de ne 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 ) = maxfD(a; b) : a; b 2 P g. Furthermore, P is called k-convex if its degree of convexity is at most k. When k = 1 we have the class LConv of Lconvex 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., rst) 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.
Proof. If P is in LR and contains two columns that are disjoint or overlapping then Dc(P ) = 2, that is P 2 LR2.
In this section we provide a decomposition for P 2 LR1(n) that is useful to obtain a set of recurrence equations for computing jLR1(n)j. 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 2 LR1(n) such that p = A(first(P )), q = A(last(P )) and i = jlow(first(P )) low(last(P )) j. Without loss of generality, in the following we suppose that p q. Indeed, by symmetry one has jLR1(n; p; q; i)j = jLR1(n; q; p; i)j.
Consider a polyomino P 2 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 polyominoes 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 )). Otherwise, 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 2 LR1(n z; p; r; j) and R0 2 R(z; e; q; k), where e; z; k; j 2 N are uniquely identi ed (q e p, q z n p r), see Fig. 2.
By considering the decomposition P = P 0 R0, we get the following partition: [ r;j;z;e;k LR1(n; p; q; i) = R(n; p; q; i) [
LR1(n
z; p; r; j) R(z; e; q; k);
(
We refer to Fig. 2 for a better understanding of the conditions on r; j; z; e; k. It
is immediate that in (
Since the set R(z; e; q; k) appears in (
R(p; p; p; 0) R(n p; r; q; j) (2) [ q+j 0r j pi i+j
Indeed, R 2 R(n; p; q; i) is the concatenation of a one-column rectangle R0 2 R(p; p; p; 0) and a polyomino R00 2 R(n p; r; q; j) for suitable r and j. Notice that the position of R00 with respect to R0 is uniquely determined by i and j, since i j = jlow(first(R00)) low(first(R0)) j, see Fig. 3.
The recurrence equations used to compute jLConv(n)j follow directly from the above decompositions. 4
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 jLConv(n)j. We developed a C++ program that computes jLConv(n)j for large n. The source code is available at: https://sites.google.com/view/polyominoesgeneration/home Table 1 shows the rst 121 values of the sequence fjLConv(n)jgn 0, (previously 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 counting sequence fcng it holds limn7!1 c1n=n = [10]. In particular, if a class of polyominoes satis es Axioms Ca1{Ca5 in [12] one has the stronger result cn =
. In our case, this means a signi cant improvement of the estimate of , from c18 = 1:6118 : : : to c120 = 1:2207.
c17 c119
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. 2. M. Bousquet-Melou.
Convex polyominoes and heaps of segments.
Journal of 3. M. Bousquet-Melou. A method for the enumeration of various classes of columnCombinatorial Image Analysis. 682, 1954. 9. Iwan Jensen. Counting polyominoes: A parallel implementation for cluster computing. In Proceedings of the 2003 International Conference on Computational
Cell growth problems. 19:851{863, 1967.