We study the family of skew polyominoes, an intermediate class between -convex and 4-stack polyominoes, defined by geometrical constraints satisfied by pairs of rows/columns. The problem of enumerating this family according to the semi-perimeter (size) is open, and can lead to a simplified enumeration of -convex polyominoes. We define a recursive method for the exhaustive generation of these objects of given size, based on generating trees. In practice, we introduce a set of operations on skew polyominoes, which perform local expansions on the objects, and such that every skew polyomino of size + 1 is uniquely generated from one of size . This leads to a simple algorithm for the exhaustive generation of skew polyominoes of size in constant amortized time.
1. Introduction
We assume the reader is confident with the concept of polyomino and with the most important
classes of polyominoes, such as the stack, the row/column convex, and the convex polyominoes.
For the main definitions concerning these objects we refer to [
In [11], the authors propose a hierarchy on convex polyominoes in terms of internal paths.
A convex polyomino is said to be -convex if every pair of its cells can be connected by a
monotone path, i.e., a path made of (unit) steps in two directions only among the four North,
East, West and South, that is internal to the polyomino and has at most changes of direction.
For = 1, we have -convex polyominoes (see Fig. 1 (b)), which have been studied by several
points of view (see [
A convex polyomino is said to be h-centered (resp., v-centered) if it contains at least one row (resp., column) touching both the left and the right (resp., top and bottom) side of its minimal bounding rectangle (see Fig. 1 (c)).
(a) (b) (c) (d)
A polyomino is said to be 4-stack if it can be decomposed into a central rectangle (supporting rectangle) supporting four stack polyominoes, one on each side of the rectangle, as graphically shown in Fig. 2. The four stacks are called, respectively, the up, right, down, and left stack of the polyomino. We denote by the class of 4-stack polyominoes. In general, a 4-stack polyomino does not have a unique decomposition in terms of supporting rectangle and four stacks (see Fig. 2). Moreover, when dealing with a certain decomposition of a 4-stack polyomino, we will always assume that the supporting rectangle is not properly included in any other supporting rectangle.
Let (resp., , , ) be the class of -convex (resp., ℎ-centered convex, 4-stack, -convex) polyominoes of semi-perimeter (size) equal to ≥ 2. Clearly, ⊆ ⊆ ⊆ (see Figures 1 and 2). The main results concerning the nature of the generating functions and the asymptotic behaviors of these families of polyominoes (according to the size) are reported in the table below.
Class of polyominoes
Type of g.f. -convex ℎ-centered 4-stack -convex convex rational rational algebraic algebraic algebraic
Asymptotic growth ︁( 1+√2 )︁ (︀ 2 + √2)︀ 4 1 83 · √4 · 4 64√ · 24 · 4 8 · 4 From these observations, Marc Noy, as reported in [14], pointed out that there should be a subclass of -convex polyominoes, strictly including the class of ℎ-centered polyominoes, growing as (4) and having a rational generating function.
So, in this paper we introduce and study the family of skew convex (briefly, skew) polyominoes,
given by 4-stacks where every pair of cells can be connected by means of a monotone internal
path using only North and East (briefly and ) unit steps, and having at most two changes
of direction. Skew polyominoes are a subclass of -convex polyominoes which includes
ℎcentered and -centered convex polyominoes (Fig. 4). We determine a recursive algorithm
for generating skew polyominoes of size based on ECO method and generating trees [
Definition 2.1.
An NE-skew polyomino is a 4-stack such that: i) for every pair of rows 1, 2 such that 1 is below 2, (1, 2) ∈ or (1, 2) ∈ holds, and ii) for every pair of columns 1, 2 such that 1 is on the left of 2, (1, 2) ∈ or (1, 2) ∈ holds.
Using the terminology of [
Generating trees and succession rules. Consider a combinatorial class , i.e., a set of discrete
objects equipped with a notion of size such that the number of objects of size is finite, for any
, and such that there is exactly one object of size 1. A generating tree for is an infinite rooted
tree whose vertices are the objects of , each appearing exactly once in the tree, and such that
objects of size are at level (with the convention that the root is at level 1). The children of
some object ∈ are obtained by adding an atom (i.e., a piece of object that increases its size
by 1) to . Since every object appears only once in the generating tree, not all possible additions
are usually acceptable. We enforce the unique appearance property by considering only those
additions that follow some prescribed rules, and call growth of the process of adding atoms
according to these rules. When the growth of is particularly regular, we encapsulate it in
a succession rule. This applies more precisely when there exist statistics whose evaluations
control the number of objects produced in the generating tree. A succession rule consists of
one starting label (axiom), corresponding to the value of the statistics on the root object, and
of a set of productions encoding the way in which these evaluations spread in the generating
tree. Obviously, the sequence enumerating the class can be recovered from the succession
rule itself, without reference to the specifics of the objects in : indeed, the -th term of the
sequence is the number of nodes at level in the generating tree. The reader interested in the
concepts of generating tree and rule of succession may refer to [
B (a)
R h r b
B (b)
R r b
B (c)
R r b
Observe that if is -centered, then ℎ = 0 (see Fig. 5 (c)), while the converse does not hold (see Fig. 5 (b)). On the other hand, if ℎ = 0 and = 1, then is -centered. 3.2. Operations on skew polyominoes necessary to understand how grows in the generating tree: To a generic ∈ , we assign a label which contains all the combinatorial information ︂(
, > 0, ℎ, ≥ 0, , , ∈ {0, 1} .
label (), being the number of cells in the rightmost column.
We will first define operations applied on a polyomino polyominoes of size + 1.
︂( . Then, to a generic ∈ , we assign the ∈ of size , producing skew all having = 1 and = 0. The labels of the produced objects are: Left Cell (LC). It can be applied to all polyominoes in , and consists in gluing a cell on the left of the basis of , in all possible positions (see Fig. 6). It produces polyominoes, still in , so we have the label ︂( - when we add the cell in the topmost position, the values of and remain how they were, - when we add the cell in a diferent position, at distance 1, . . . , − 1 from the topmost position, the value of always becomes 0, while remains how it was before, so we have ︂( ℎ + 1 1 )︂ 0 0 , . . . , ︂( ℎ + − 1 1 )︂
.
B
R 0 h r b
B 0
R produced objects are: Right Cell (RC). It can be applied to all polyominoes in , provided = 1 to avoid ambiguity. It consists in gluing a cell on the right of the basis of , in all possible positions, and produces polyominoes, still in , all having = = 1 and ℎ = = 0 (see Fig. 7). The labels of the - when we add the cell in the topmost position of the basis, the obtained polyomino ′ has ( ′) = ( ), while ( ′) = 1 if and only if ( ) = 1, so we set ( ′) = ( ), getting h r b the labels
B
R the label ︂( position of the basis, and become 0, so we have − 1 labels as
B
R
B
R still in , with label ︂( ℎ + 1 )︂ 1
.
Row. It consists in adding a new row to the basis of (see Fig. 8). It produces one polyomino, h r b B
R
.
b h r b
B
R R operation can be applied only to polyominoes such that: i) = 1, so that the addition of the new cell does not violate the convexity of the polyomino; ii) = = 1, to ensure that the polyomino has not been yet obtained by means of the operation LC (i.e., = 0) or Row (i.e., > 1). Summing up, provided = = = 1, there are two cases where the operation Top can be applied: (T1) is not -centered (see Fig. 9 (a)). In this case, ℛ coincides with ℬ, so ℎ > 0 and = 0. The application of Top to a polyomino of this kind just increases by one the value of ℎ, while the values of all the other parameters remain the same, giving the production the vertical basis does not include the last column of , then applying Top we obtain a polyomino ′ which fits in case (T1), ( ′) = 0 and ℎ( ′) = ( ) + 1. So, the production for this case can be described by The productions for both cases (T1) and (T2) can be written as
R t = 0
R t = 0
R t=0
R t = 0 R t = 1
R t = 0
R t = 0
R t = 1 r b B r b B r b (a) B
R B (b) (c)
B
Parall. This operation can be applied to all polyominoes in , provided ℎ ≥ 1 or ≥ = 1 (for ambiguity reasons). It consists in gluing a column of length , with 2 ≤ ≤ ℎ + + 1, 1, and h r b r b r b
B B B ︂( R ︂( ︂( on the right of the basis of , with the lowest cell being glued to the topmost cell of the right side of the basis. It produces + ℎ polyominoes still in , with = 1. Two cases may occur: (P1) ℎ > 0. The polyomino is not -centered and has label us consider separately the cases: ︂( - if 2 ≤ ≤ + 1 (r-Par), the addition of the new column does not change the canonical - if + 2 ≤ ≤ + ℎ + 1 (h-Par), then, for each of the obtained polyominoes, the canonical rectangle coincides with its basis and has height equal to 1. So, = 0, and the labels are (P2) ℎ = 0. Here, is -centered, and necessarily > 0, so its label is ︂( 0 )︂ 0 1
In this case, only columns of length 2 ≤ ≤ + 1 can be added, and the addition of the new column does not change the canonical rectangle ℛ (Fig. 10 (b), (c)). It gives the same labels of the production r-Par of the previous case, except for the last production, corresponding to adding a column of length + 1. In this case, the obtained polyomino ′ has ( ′) = ( ), so we have labels: ︂( 0 1 1 )︂ (︂ polyomino of this kind we can only apply the operation Right Stack (RS). It consists in gluing a column of length , with 1 ≤ ≤ produces (︀ +1)︀ polyominoes in , with labels (1) (2)− 1 . . . ( −
2 all possible ways. This operation can be applied to all polyominoes in , provided ≥ side of , in the area belonging to ℛ and above ℬ (taken into account by the parameter ), in notation stands for repetitions, i.e., with 1 ≤ ≤ the label () is produced − + 1 times. A polyomino ∈ has label () given by the length of the rightmost column of . To a , to the right Right Stack*, analogous to Right Stack defined for polyominoes. It consists in gluing a column of length , 1 ≤
≤ This operation produces (︀ +1)︀ polyominoes in , with labels (1) (2)− 1 . . . ( − 1)2 () . 2
, to the right side of the last column of , in all possible ways.
Theorem 3.1. Every skew polyomino of size + 1, with ≥ skew polyomino of size through the application of one among the operations LC, RC, Row, Top, 2, is uniquely generated from a
Proof. To prove the statement, we just need to show that, given a skew polyomino of size + 1, ≥ 2, there is a unique skew polyomino ( ) of size such that is generated from ( ) applying exactly one of the operations defined above. Let us consider all the possible, mutually disjoint, cases: 1) ∈ (not ℎ-centered). Then, is obtained by adding the rightmost column to the polyomino ( ): if ( ) ∈ , by performing Right stack, while if ( ) ∈ , by performing Right stack* (Fig. 11 (a)). 2) ∈ (ℎ-centered). Then, we have the following disjoint possibilities: > 1: Then, the last applied operation is Row (Fig. 11 (b)). = 1 and = 0: An exhaustive check reveals that there is only one operation that produces polyominoes with = 0 and = 1, and it is precisely LC. Then, is produced by applying LC to the polyomino ( ), obtained from by removing the first column (see Fig. 11 (c)). = 1 and = 1: We can consider two possibilities: the last column of has exactly one or more than one cell.
In the first case, we observe that the last applied operation needs to be one among LC, RC, Right stack and Right stack*, whereas the last two are not possible, since is not in . Moreover, since = 1, also LC cannot be the last applied operation. Then, the last applied operation is necessarily RC, and it is applied to the polyomino ( ) obtained from by removing the cell in the last column (see Fig. 11 (d)).
In the second case, the last column of has more than one cell. The only possibility is that the first column ′ of contains no cell above the basis, and at least one cell below it; the last column ′′ of contains at least one cell above the basis, and no cell below it. So, the columns ′, ′′ are in relation , precisely (′, ′′) ∈ , and ℛ = ℬ. Again two cases arise: on one hand, the top side of ′′ has ordinate greater than all other cells in . Then, the last applied operation is Top (Fig. 11 (e)). On the other, the top side of ′′ has ordinate smaller than or equal to the top side of the column on its left. Removing ′′ from , we have a (ℎ-centered) polyomino ( ) of size . Moreover, since ( ) = 1, can only be obtained by gluing ′′ on the right of the topmost right cell of the basis of ( ) (Fig. 11 (f)). So, the last applied operation is Parall. We conclude by noticing that no other possible cases arise.
The growth of the generating tree can be formally expressed by the following two succession rules. The first, Ω , describes the growth of polyominoes in , Ω : ⎧ (︂ 0 0 1 )︂ ⎪ 1 0 1 ⎪⎪⎪⎪ (︂ ℎ )︂ ⎪⎪⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ (if = = = 1) ⎪ ⎪ ⎪ ⎨
(if = 1) ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ (if > 1) (if > 0, ℎ = 0) → (if > 0, ℎ > 0) → The second rule, Ω, describes the production of the labels () of elements in , Ω : () →
(1) (2)− 1 . . . ( − 1)2 () RS*. (a) (d) (b) (e) (c) (f)
The first few levels of the generating tree, with the corresponding labels, are depicted in Figure 12. From the generating tree we can generate the first terms of the sequence of skew polyominoes of size ≥ 2:
We point out that this sequence is not yet included in the Online Encyclopedia of Integer
Sequences [17]. Using standard techniques ([
Row
Left Cell
Right Cell
Row
according to the size. In some further research we plan to solve this system, by applying
a generalization of the classical kernel method, known under the name of obstinate kernel
method ([
IWCIA 2014., Lecture Notes in Computer Science, vol 8466. Springer [11] G. Castiglione, A. Restivo, Reconstruction of -convex Polyominoes, Electron. Notes Discrete
Math. 12, Elsevier Science (2003) [12] M. Delest, X. Viennot, Algebraic languages and polyominoes enumeration, Theor. Comp.
Sci. 34:169–206 (1984) [13] A. Del Lungo, E. Duchi, A. Frosini, S. Rinaldi, On the generation and enumeration of some classes of convex polyominoes, Electronic Journal of Combinatorics 11, #R60 (2004) [14] E. Duchi, S. Rinaldi, G. Schaefer, The number of -convex polyominoes, Adv. Appl. Math.
4:54–72 (2008) [15] J.M. Fedou, A. Frosini, S. Rinaldi, Enumeration of 4-stack polyominoes, Theor. Comp. Sci.
502:88–97 (2013) [16] A.J. Guttmann, P. Massazza, Asymptotics of -convex polyominoes, RAIRO-Theor. Inf.
Appl.58 (2024) 12 [17] OEIS Foundation Inc., The On-line Encyclopedia of Integer Sequences, http://oeis.org (2011)