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.