Moving from the seminal work of Beauquier and Nivat (1991) about the characterization of polyominoes that tile the plane by translation, Blondin Massé et al. (2013) found that their boundary words, encoded by the Freeman chain coding on a four letters alphabet, have interesting combinatorial properties. In particular, they considered the specific class of double square polyominoes, and they defined two operators that allow to generate them starting from the basic class of the so called prime double squares. However, the proposed algorithm sufers few drawbacks due to repetitions and outliers generation. Here a diferent combinatorial approach to the double square characterization is proposed. In particular we provide a series of properties for the boundary words of prime double square tiles, that lead to detect some factors of them where a specific letter of the alphabet never occurs. The possibility of extending this property to the whole boundary word of a prime double square, as it seems, would naturally provide a valuable characterization and a tool for their generation and enumeration.
represented as a set of cells on a squared surface, each square being associated to an integer point.
through properties of the Freeman chain coding on a four letters alphabet of their boundary. In particular, the boundary word of an exact polyomino, say tile, can be factorized according to the equation = 123̂︀1̂︀2̂︀3, where ̂︀ refers to the word considered as a path and travelled in the opposite direction. We will refer to such decomposition as BN-factorization.
squares in this case, pseudo hexagons otherwise.
in a tiling, with four or six copies of itself, respectively, see Fig. 1() and (). It is easy to verify that some tiles also show these two behaviours at the same time in a tiling, as witnessed in
(a) (b) (c)
as a pseudo square in at most two distinct ways. Furthermore, if two diferent pseudo square factorizations of exist, then no decomposition as a pseudo hexagon does. The authors refer to these exact polyominoes as double squares.
of their exhaustive generation. To hit this target, in [5] two operators have been defined and recursively applied to a basic subclass, say prime double squares, defined throughout the notion of homologous morphism. Unfortunately, those operators sufer from some drawbacks: in particular, as observed by the authors, their iterative application may not generate a double square polyomino, or may generate more copies of the same double square (see Fig. 12 in [5]).
alphabet Σ. Then, for any letter ∈ Σ, is not a factor of .
In this article we move from the results in [1] and we show that the boundary word of a prime double square has a peculiar form that involves factors that are repeated in diferent parts of both the BN-factorizations. We also prove that some of these factors are characterized by the absence of specific letters of the coding alphabet. This result opens a promising way both to the enumeration and to the generation of prime double squares (lately, of all the double square polyominoes), since it allows to generate parts of their boundary words whose path does not self intersect. So, in the next section we recall some basic definitions on combinatorics on words and few preliminary results to approach the study of prime double square polyominoes. Then
Let us consider the lattice grid Z2. A polyomino is defined as a 4-connected finite subset of points of Z2. Each polyomino can be represented as a finite set of cells on a squared surface, each cell representing a lattice point (see Fig. 2). It is commonly required that polyominoes have no holes, i.e., the boundary of their representation as a set of cells is considered as a continuous, closed and non-intersecting path. We adopt this assumption here. Relying on that, we naturally code the boundary of a polyomino through a word, say boundary word, on an alphabet of four letters, Σ = {0, 0, 1, 1}. Each letter of the word represents a step in one of the four directions of the discrete grid, {→, ← , ↑, ↓} respectively. Due to the correspondence between letters of Σ and directions, we indicate 0 and 0, resp. 1 and 1, as opposite. Figure 2 shows an example of the coding.
Obviously, choosing diferent starting points and moving along the border clockwise or counterclockwise lead to diferent boundary words for the same polyomino. So we need to introduce the following definitions to overcome these ambiguities. Using the standard notation, we indicate with Σ* the free-monoid on Σ, i.e., the set of all words defined on Σ, where is the empty one, and with Σ+ the set Σ* ∖ {}. Given ∈ Σ* , || denotes its length, while || is the number of occurrences of the letter in the word . The notation indicates the concatenation of copies of the word . Finally, is a factor of if there exist , ∈ Σ* such that = . If = [resp. = ], then is a prefix [resp. sufix ] of , while if || = || then is the center of . The notation ∈/ points out that is not a factor of .
Two words and are conjugate, say ≡ , if there exist two words and such that = and = . The conjugacy is an equivalence relation, and the conjugacy class of a word contains all its cyclic shifts, i.e., all the possible coding of a polyomino when fixing a travelling direction and moving all over the possible starting points. We decide to describe the boundary of a polyomino by travelling it clockwise, in order to identify it with any word of the class (see again Fig. 2 for an example). The unit square turns out to be = 1010. Moreover, if is the boundary word of a polyomino, the following conditions hold: for all ∈ Σ we have | | = | | (this ensures the closeness of the boundary), and there exists ∈ Σ such that || ̸= || for any proper factor of (this ensures that the polyomino is 4-connected). We define three operators on a word = 12 . . . ∈ Σ* :
with its opposite; 2. the reversal of , indicated with ˜, is defined as ˜ = − 1 . . . 1. A palindrome is a word s.t. = ˜; 3. the hat of w, indicated with , is the composition of the previous operations, = ˜.
̂︀ ̂︀
which we are interested. A polyomino is called exact if it tiles the plane by translation. Beauquier
and Nivat characterized exact polyominoes in relation to their boundary word, providing the
following
Theorem 1 ([2]). A polyomino is exact if and only if there exist 1, 2, 3 ∈ Σ* such that
= 123̂︀1̂︀2̂︀3,
where at most one of the words is empty. This factorization may be not unique.
We will refer to this decomposition as a BN-factorization, and call BN-factors the words and
̂︀ provided by the decomposition. Starting from this result, exact polyominoes can be further
divided in classes; we will focus on pseudo squares, that are the exact polyominoes where one of
the BN-factors is empty. Among them, we specify the double square polyominoes, that admit
two diferent (in terms of BN-factors) BN-factorizations as a square, ̂︀̂︀ ≡ ̂︀ ̂︀ . Due
to the presence of two BN-factorizations, double squares’ boundary words can be written in the
general form obtained from Corollary 6 in [6],
= 12345678,
(
We introduce the notion of homologous morphism. A morphism, in our framework, is a function
: Σ* → Σ* s.t. ( ) = ( ) ( ) with , ∈ Σ, i.e., it preserves concatenation, and it is
said to be homologous if, for all ∈ Σ* , (̂︀) = ˆ(︁), i.e., it preserves the hat operation. From
now on, we will refer to homologous morphisms only. For each exact polyomino = ̂︀̂︀,
we can define the trivial morphism that maps the unit square in as (
not be obtained by composing two or more diferent morphisms. This last class, that constitutes the basis for the generation of double squares through homologous morphisms, will be the focus of our work. In particular, we will provide some properties of their boundary words setting the path for a suitable characterization to generate and then enumerate them.
. . . . . .
Example 1. The double square = 11 .. 01011 .. 010 .. 11010|11 .. 01011 .. 010 .. 11010 is not
prime, since it can be obtained applying to the unit square, in this order, the morphisms (0) = 010,
(
.
The notation .. separates the factors in , while | denotes half of the word.
On the other hand, the cross polyomino in the intermediate step is clearly prime. ϕ ψ
Property 1 ([5]). Let be a double square, and ̂︀̂︀ ≡ ̂︀ ̂︀ its BN-factorizations. If is prime, then the factors , , , are palindrome.
Property 2 ([5]). Given = 12 . . . 8 the boundary word of a double square as in (
̂︀− 3− 1 = .
Theorem 2 ([1]). If is the boundary word of a (prime double square), then it fits in one of the two following forms: a) b)
. . . . . .
= (1˜1)1 1 .. ˜1 .. (1˜1)3 3 .. ̂︀1|(1̂︀1)1 1 .. ̂︀1 .. (1̂︀1)3 3 .. ˜1, with and palindrome and 1, 3 ≥ 0,
. . . . . .
= 1 .. (˜31)2 ˜1 .. 3 .. (̂︀13)4 ̂︀1|1 .. (̂︀31)2 ̂︀1 .. 3 .. (˜13)4 ˜1, with 2, 4 ≥ 0, where the factors are those ones provided by Property 2 and under the assumption that |1| ≤ |2|, |3|, |4|, so that 2 = ˜1 and 4 = ̂︀1.
Theorem 3 ([1]). Given a , its boundary word is couple-free, i.e., no two consecutive occurrences of a same letter of Σ are present.
Proposition 1. Let be the boundary word of a pds having form b) of Theorem 2. Then, it is always possible to rephrase in the form a) of Theorem 2.
the choices of 1, 3, , and the values 1, 3 ≥ 0.
This section is dedicated to the study of the factor 1 of a pds’ boundary word in the form a) of Theorem 2, providing the main result of Theorem 4. In particular, we will show that the non-self intersection property of the boundary word of a pds implies that 1 contains three letters only. To simplify the proofs, we will assume 1 = 3 = 0, so obtaining the boundary word of a pds in the form
. . . . . ..
= 1 .. ˜1 .. 3 .. ̂︀1|1 .. ̂︀1 .. 3 . ˜1,
(
the BN-factors = 1˜1, = 3̂︀1, = ˜13 and = ̂︀1 1.
Lemma 1. Let = ̂︀̂︀ ≡ ̂︀ ̂︀ be (the boundary word of) a pds. For each factorization, the four BN-factors begin (and end) with a diferent letter of the alphabet Σ = {0, 0, 1, 1}.
equal letters occur in (see [1]).
as a consequence, starts with 0 and with 1, since the polyomino is travelled clockwise in both factorizations.
Proposition 2. Given a pds as in Eq. (
and begin with 0 and 1, respectively, so that starts with 0 (from ) and ends with 0 ( is palindrome). Again by palindromicity, we obtain that the last letters of 1 and 3 are respectively 1 and 0. □
Theorem 4. Given a pds with boundary word expressed as in Eq. (
is assumed that only one occurrence of 1 is present in 1, i.e., 1 = 111 with 1 ∈/ , and , ̸= . Similarly, a contradiction is obtained if we assume that more occurrences of 1 are present in 1.
Proof of Theorem 4
Lemma 2 ([7]). Assume that = = , with ̸= . Then, for some palindromes , ∈ Σ+ and some ≥ 0, we have = , = () and = .
Lemma 3. Let 1, 2, 3 ∈ Σ+ be three palindromes such that 123 is palindrome too. Then, for some palindromes , ∈ Σ+, 1, 2 and 3 can be obtained as their alternate concatenations.
Lemma 4. Let us assume 1 = 111 with 1 ∈/ , . Then, both and have length ||, || > 1.
Lemma 5. Let us assume that 1 = 111 is a factor of the boundary word of a pds expressed
as in Eq. (
̂︀ ̂︀ Let us suppose 1 ∈ 3 and, as a consequence, 1 ∈ too. We make the first occurrence in 3 explicit, 3 = 1 with 1 ∈/ . From palindrome, we get 1′ = ˜1 for a suitable ′ s.t. = ′1; we also notice that 1 ∈/ ′. We now analyze the length of the words and : 1. Case || < ||. There exists a factor ′ such that = ′˜ and 1′ = ˜′1. We now move to the other BN-factor, = 3̂︀1, to study its palindromicity.
We have = 111′1 palindrome and, since 1 ∈/ , || ≤ | |. As a consequence, if
̂︀ ̂︀
the inequality is strict, we can write the last palindrome as = ′1˜. It follows from the
palindromicity of that 1̂︀1′1′ has to be palindrome too. Even in this case, we
̂︀
can deduce || ≤ | ′| from the property 1 ∈/ . If the inequality is strict, then || < |′|
and, for the same reason, the letter 1 in boldface is part of the factor . We also remind
that 1 ∈/ , then the factor is made of one letter only, = 0 or = 0, in contradiction
with Lemma 4. Then || = |′|, and we get that 1′ in is palindrome. The letter
̂︀ ̂︀
in boldface is the only occurrence of 1, so the center, and then ′ is the empty word. It
follows that = ˜, so 1 is palindrome, and = 3. Studying again , we immediately
argue that 3 = too. We can now define a non-trivial morphism, (0) = 3, (
We finally have to study the case (1 ∈/) = , that gives in the palindrome 1̂︀1′. ̂︀
or not. If ′ = 1, then from 1′ = ˜′1 we get ′ = 1. Then starts with ′ and 3 ̂︀ ends with , that is impossible since they both start and finish with the same letter 0 (see Proposition 2). Then, there exists ′ such that = ′̂︀1′ and ′1 is palindrome. From ̂︀ this last condition, we argue that the second letter of is 1, since || = 1 does not hold by Lemma 4. We now study the palindrome ′1: ̂︀ i) |′| < ||. In this case, there exists ′ such that ̂︀ = ̂︀′˜′, i.e. = ′′, and 1 ∈/ ′.
So, = (′1)(1˜1˜1)(1) = ′1′′˜′1′1˜1˜11′′˜′1′. Since 1 ∈/ ′ and ̂︀ ̂︀ 1 ∈/ ′, it must be ′ = ′ = 0 (we remind that starts with 0 by Proposition 2). Then, = 01′′010 is not palindrome, contradiction. If |′| = ||, then ′ = , ̂︀ so that 1 ∈/ ′ and the same contradiction is reached. ii) || < |′|. In this case, there exists a palindrome ′′ ̸= such that ′ = 1′′. We get 1 = 111, 3 = 1 = 111′′ = 1′′, = ′1 = ′111′′ = ′1′′ and ′′ palindrome, with 1 ∈/ , ′, , . The boundary word of the pds is now . .. .
= 1 .. ′1′′˜1 . 1′′ .. ̂︀1| . . . , and = 1˜1 is palindrome if and only if ′1′′ = ′111′′ is palindrome. Since 1 ∈/ ′ and || > 1, we argue that ˜′ is a sufix of ′′, ′′ = ′′′˜′ palindrome, and 1′′′ is palindrome too. Moving to = ′1′′′˜′˜11′′′˜′, we deduce that ˜′˜1 is palindrome with one only occurrence of 1 (that one in 1). So, = ′ and 1 are palindrome. We get
. .. .
= 1 .. 1′′′1 . 1′′′ .. 1| . . . with 1′′′ and ′′′ palindromes (since center of the BN-factors and , respectively). In particular, ′′′ ends with 1 and, since 1 ∈/ , there exists a palindrome such that ′′′ = , with and 1 both palindrome. By Lemma 3, there exist two palindromes 1 and 2 such that 1, and can be written as their concatenation.
1 contains occurrences of both the letters 1 and 1.
We finally get that 1, , 3 and are concatenation of the palindromes 1 and 2 (or
their opposite), and then it is possible to define a non-trivial morphism, (0) = 1,
(
The case || = || immediately gives a contradiction through the definition of a morphism ,
as shown before. We then conclude that no occurrences of the letter 1 appear in the factor 3.
So, from the palindromicity of , we argue that |3| ≤ | |. If 3 = palindrome, then ˜ =
and 1 is palindrome too. Going back to the BN-factor , we get = 3 and a non-trivial
morphism (0) = 3, (
Being = 3111, there exists ′ such that = ′1˜3 and 11′ are palindrome. Since ̂︀ ̂︀ ̂︀ ̂︀ 1 ∈/ 3 and is palindrome too, we can write the factor as = 3′′1˜3 for a suitable ′′. From , we obtain that ̂︀113′′1˜3 is a palindrome. This leads to a last contradiction since 1 ∈/ 3 ̂︀ and |1| ≤ | 3| by hypothesis. □
Corollary 1. Since 1 ∈ 1 is unique and it is not the center of , it follows that |3| ̸= ||. We continue the analysis of the position of 1 ∈ 1 in the BN-factor = ˜13. As final result, we will obtain that there are no available positions for it in .
Lemma 6. Let us assume that 1 = 111 is a factor of the boundary word of a pds expressed
as in Eq. (
Proof. Since 1 is in the first half of = ˜13, we have that || < |3|, and 3 = 11 for a proper non-empty such that ˜1 is palindrome. We now distinguish two cases. 1. || < ||, and = 1 for a proper palindrome ∈ Σ+. Replacing in the factor, we get 3 = 1, where we remark that ̸= since 3 starts with 0 and 1 with 1 (see
= 3̂︀1 = 1̂︀1 = 1111̂︀1̂︀1.
(
The case = can be studied similarly to case 2, due to 1 ∈/ .
□
in both cases of Lemma 6 can be performed similarly to the study of the palindromicity of = ˜13 with 1 ∈ 1, where 3 is replaced with ′′ or ′′.
Lemma 7. Let us assume that 1 = 111 is a factor of the boundary word of a pds expressed
as in Eq. (
If ′ = ˜13, then |3| < |′| < || < |1|, in contradiction with the assumption on the mutual lengths of the factors . So, 3 = 1′ for a proper such that ˜1 is palindrome, and we get the thesis of case ). The same occurs if ′ = . □
palindromicity of can be performed as the study of = ˜13. In case ), just replacing with ′′; in case ) we are in the same case of Lemma 6, where ′ replaces the sufix 1 of 3 and 1 ∈ 1 is in the first half of .
Theorem 5. If 1 = 111, there exist , , ≥ 0 and a palindrome ∈ Σ+ such that = (1) , 3 = (1) and = (1) . Moreover, 1 is palindrome.
apply Lemma 6 and Lemma 7, according to the length of the involved factors, and to finally obtain that 3, and are concatenation of 1, ˜1, and ˜ for some ∈ Σ+. The palindromicity of 1 and is deduced by the fact that both and are palindrome at the same time, up to the parity of .
If Lemma 6 is never applied during the iterative proof, then = 3. Indeed, in this case we have that 1 is palindrome, = (1) and 3 = (1) for a non-empty palindrome and , ≥ 0. Since is a pds, its BN-factor = 3̂︀1 is palindrome, that is = (1) 1 palindrome. We can apply Lemma 3 with 1 = 3, 2 = 1 and 3 = . Since 1 is not a factor of , the possible case is 1 = 3, i.e. = 3 = (1) . □ Hereafter we provide an example where one only iteration of Lemma 6, case 1, ) in the proof, is suficient to express the BN-factors and in terms of 1 and . In this case we get = = ′′ = and, as a consequence, 3 = 11 ||<|| 1 ||<|| 1′′1,
= =
and ′′ = since is palindrome and, by hypothesis, the proof stops here after one single
iteration. Then, the boundary word can be obtained applying the non-trivial morphism
. . . . . .
(0) = , (
Corollary 2. 1 = 111 can not be a factor of the boundary word of a pds expressed as in
Eq. (
Proof. If 1 = 111, from Theorem 5 we know that 1 is palindrome, = (1) , 3 =
(1) and = (1) for some palindrome and , , ≥ 0. Then, it is possible to
define an homologous morphism, (0) = and (
we include 1 in 1: in the first, the boundary of the pds self intersects, while, in the former, the polyomino can be obtained from the unit square through the composition of more than one non-trivial homologous morphism.
Example 2. Let us consider 1 = 101010101010101. We can choose = 010 and 3 = 010101010101010 to construct the (palindrome) BN-factors = 1˜1 and = ˜13. The boundary word we get is and self intersects (boldface letters), so it does not define a polyomino.
On the other hand, choosing 1 = 101010101, = 01010 and = 3 = 1 we get the double square 2 = (10101010101010)410101010101010| . . . .
The polyomino is well defined and the boundary does not self intersect. However, it is not prime since a non-trivial morphism can be easily defined.
starting from the basic class of prime ones. By a combinatorial approach, we started to characterize their boundary words in terms of one single letter’s absence. The obtained results suggest the possibility of extending such property to the other factors of the boundary word, so providing a valuable tool (alternative to [5]) to characterize and successively generate and enumerate them.
CUP_E53C22001930001) "Combinatorial and enumerative aspects of discrete structures: strings, hypergraphs and permutations".