Tiling of dominoes with ranked colors

Abstract

Several articles deal with tilings with various colors and shapes. In this paper, we present a new type of tiling problem of a $(1\times n)$—board where the colors have a prescribed order of preference and the size of colored dominoes is bounded by $(1\times s)$. We show that the total number of tilings can be given as a linearly recurrent sequence of order ks, and at the same time by a higher order self-convolution of s-generalized Fibonacci sequences.

1 Introduction

The investigation of tiling problems has been an intensively researched area of combinatorics. The researchers consider different shapes and colors of tiles, different boards, and different tiling rules.

Let $r_n$ be the number of different tilings with $1\times 1$ squares and $1\times 2$ dominoes (two squares with a common edge) of a $(1\times n)$—board. It is known that these tilings can be counted by the Fibonacci numbers (see, for example, Benjamin and Quinn [1]). In fact, $r_n=F_{n+1}$ is the shifted Fibonacci sequence (as usual, $F_n$ is defined by $F_n=F_{n-1}+F_{n-2}$, $F_0=0$, $F_1=1$, and associated with A000045 in The On-Line Encyclopedia of Integer Sequences (OEIS) [2]). Considering the squares and dominoes, respectively, in a and b different colors, one finds $r_{n}=a\, r_{n-1}+b\, r_{n-2}$ for $n\ge 2$ with the initial values $r_0=1$, $r_1=a$ (see Refs. [1, 3]). Obviously, if $a=b=1$, then we obtain the classical solution $r_n=F_{n+1}$. Koshy [4, Chapter 33] defined the weight of a square to be x and that of a domino to be 1. This weighting provides combinatorial models for Fibonacci and Lucas polynomials using linear and circular tilings, and in that way, a general discussion of the tiling with squares and dominoes. The author has not only given the number of tilings made up of colored tiles but has also given a number of combinatorial identities of the Fibonacci and Lucas numbers using the well-known Fubini principle (counting objects in a set in two different ways gives the same result). In Ref. [4, Chapter 42], the reader can find similar models for the Chebyshev polynomial with different weightings of squares and dominoes.

It is also well-known that for $s\ge 2$ the sequence of s-generalized Fibonacci (or s-bonacci, or s-Fibonacci) numbers $F^{(s)}_{n+s-1}$ gives the number of tilings on a $(1\times n)$–board with unicolored dominoes having maximal size $1\times s$ [5]. As usual, the sequence $(F^{(s)}_{n})$ is defined by the recurrence $F^{(s)}_{n}=F^{(s)}_{n-1}+F^{(s)}_{n-2}+\cdots + F^{(s)}_{n-s}$ with $F^{(s)}_{0}= F^{(s)}_{1}= \cdots =F^{(s)}_{s-2}=0$, $F^{(s)}_{s-1}=1$. Clearly, $F_n=F^{(2)}_{n}$ holds for $s=2$. The first few k-generalized Fibonacci sequences appear in (OEIS) [2], see A000045, A000073, A000078, A001591, A001592, A066178, A122189, A079262.

For a recent identity concerning the connection of s-generalized Fibonacci sequences and tilings, see Ref. [6]. Certain new results on s-generalized Fibonacci sequence were published by Belbachir and Belkhir [7], further Komatsu et al. [8]. Komatsu and Laohakosol [9] investigated some reciprocal sums of generalized Fibonacci sequence.

In the previous works, all colors had the same meaning, they had no order of importance. In contrast, in this article, unusually, we give preference rank to colors. We think that this new approach of tiling could trigger further investigations.

Let $n\in \mathbb {N^+}$ and consider the domino tilings of a $(1\times n)$—board with the following properties.

Condition 1.:

Every domino has a color from the color set $\{C_1,C_2,\ldots , C_k\}$, $1\le k\in \mathbb {N}$.

Condition 2.:

The size of a domino (in each color) is one of $1\times \ell$, where $\ell$ is a positive integer with $1\le \ell \le s$.

Condition 3.:

In the tilings, there exists a preference rank of colors such that color $C_j$ cannot be used before color $C_i$ (from left to right) if $i<j$.

As an example, Fig. 1 illustrates all the tilings for $n\le 3$, $s=3$, when $k=3$ and the colors $C_1$, $C_2$, and $C_3$ are black, grey, and white, respectively. We note that if $n\le 3$ and $s\ge 3$, then we cannot use dominoes longer than 3. Thus, for example, for $s=4$ Fig. 1 even shows all the tilings for $n\le 3$, $k=3$.

Fig. 1

All tilings with colors $C_1$, $C_2$, and $C_3$ (black, grey, and white) if $n\le 3$ and $s=3$

In the present work, we examine the number $T_{k,s}(n)$ of possible tilings with the conditions above. The main result gives $T_{k,s}(n)$ as a recursive sequence of n with parameters k and s. Note that

$$\begin{aligned} T_{k,s}(0)=1, T_{k,s}(1)=k, \text { and } T_{k,s}(n)=T_{k,s+1}(n) \text { for all } s\ge n \end{aligned}$$

(1)

hold trivially. It turns out that the order of the recurrence is ks. The main tool is the method developed in Ref. [10, Theorem 2], which gives the characteristic polynomial of the component sequences of a suitable vector recurrence, and of $T_{k,s}(n)$ at the same time. We remark that Németh and Szalay [11] described the sequence $T_{k,2}(n)$ recursively as a corollary of a result on a specific system of two recurrence sequences with order s. The second important observation in this work is that the number $T_{k,s}(n)$ of tilings can be provided by a self-convolution of s-generalized Fibonacci sequences.

In the next subsection, we prepare the machinery we need in the proof of Theorem 1 later. Section 2 studies the tiling problem in detail; the main result (Theorem 1) is illustrated in the cases $k=2$ and $k=3$. For larger k values, the precise computation becomes more and more difficult from technical point of view. Moreover, we present one-to-one correspondence between the binary strings and our tilings. Finally, the convolution approach will be presented.

1.1 Vector Recurrences

Now we turn our attention to the basic tool we will apply to solve our tiling problem.

As before, let $k\ge 1$ and $s\ge 1$ denote two positive integers. Assume that there are given the matrices $\textbf{A}_t=\left[ a_{i,j}^{(t)}\right] \in \mathbb {C}^{k\times k}$ for $t=1,2,\dots ,s$. Define the vector recurrence

$$\begin{aligned} \textbf{v}_n=\textbf{A}_1\textbf{v}_{n-1}+\textbf{A}_2\textbf{v}_{n-2}+\cdots +\textbf{A}_s\textbf{v}_{n-s},\qquad n\ge s \end{aligned}$$

(2)

with initial column vectors $\textbf{v}_{0},\textbf{v}_{1},\dots ,\textbf{v}_{s-1}\in \mathbb {C}^k$. One important endeavor is to separate the component sequences of the vectors $(\textbf{v}_n)$ and find a common linear recurrence relation to describe them. The main advantage of our solution is the uniform treatment and the possibility of automatism. This is given in Ref. [10, Theorem 2.1], and can be formulated as follows. Let $\textbf{I}_k$ denote the $k\times k$ unit matrix.

Lemma 1

The common characteristic polynomial of the component sequences of $(\textbf{v}_n)$ is

$$\begin{aligned} p(x)=(-1)^{s}\det \left( \textbf{A}_s+x\textbf{A}_{s-1}+x^2\textbf{A}_{s-2}+\cdots +x^{s-1}\textbf{A}_1-x^s\textbf{I}_k\right) . \end{aligned}$$

This lemma is the key tool in determining the number of the tilings presented above. We note that $ks^2+ks-s^2$ was the exponent of $-1$ we computed originally, but $(-1)^s$ gives an equivalent coefficient to the determinant since $ks^2+ks$ is always even.

2 Tiling with Colored Dominoes

In this section, we find the characteristic polynomial of the recursive sequence $(T_{k,s}(n))$ and the exact recurrence relations for $k=2$ and $1\le s\le 7$.

Theorem 1

The characteristic polynomial of the recursive sequence $(T_{k,s}(n))$ is

$$\begin{aligned} p(x)=(1+x+\cdots +x^{s-1}-x^s)^k. \end{aligned}$$

It implies immediately that the order of recursion which determines $(T_{k,s}(n))$ is ks.

Proof

Under Conditions 1–3, let $c_{i}(n)$ ($1\le i\le k$) denote the number of different tilings of a $(1\times n)$-board when the last domino has color $C_i$. (Note that here we do not denote the parameter s.) Clearly, $T_{k,s}(n)=\sum _{i=1}^kc_i(n)$.

It follows from the constraints that

$$\begin{aligned} c_i(n)=\sum _{j=1}^ic_j(n-1)+\sum _{j=1}^ic_j(n-2)+\cdots +\sum _{j=1}^ic_j(n-s),\quad n\ge s \end{aligned}$$

(3)

holds for any $1\le i\le k$. (See also [11] for the case $k=2$.) If we consider $c_i(n)$ as the ith component of the vector $\textbf{v}_n$, then we obtain a particular case of the vector recurrence (2). Indeed, writing out (3) in details we find

$$\begin{aligned} c_1(n)= & c_1(n-1)+c_1(n-2)+\cdots +c_1(n-s),\\ c_2(n)= & c_1(n{-}1)+c_2(n-1)+c_1(n{-}2)+c_2(n{-}2){+}\cdots {+}c_1(n-s)+c_2(n{-}s),\\&\vdots&\\ c_k(n)= & \sum _{j=1}^kc_j(n-1)+\sum _{j=1}^kc_j(n-2)+\cdots +\sum _{j=1}^kc_j(n-s). \end{aligned}$$

This system can be also given in the form (2) with matrices

$$\begin{aligned} \textbf{A}_1=\textbf{A}_2=\cdots = \textbf{A}_s= \begin{pmatrix} 1& \quad 0& \quad 0& \quad \cdots & \quad 0 \\ 1& \quad 1& \quad 0& \quad \cdots & \quad 0 \\ 1& \quad 1& \quad 1& \quad \cdots & \quad 0 \\ \vdots & \quad \vdots & \quad \vdots & \quad \ddots & \quad \vdots \\ 1& \quad 1& \quad 1& \quad \cdots & \quad 1 \end{pmatrix}\in \mathbb {C}^{k\times k}. \end{aligned}$$

Put

$$\begin{aligned} \textbf{B}_s(x)=\textbf{A}_s+x\textbf{A}_{s-1}+x^2\textbf{A}_{s-2}+\cdots +x^{s-1}\textbf{A}_1-x^s\textbf{I}_k. \end{aligned}$$

Since all $\textbf{A}_i$ are equal, we can denote them by $\textbf{A}$. Moreover, let $x_s=1+x+\cdots +x^{s-1}$. Then

$$\begin{aligned} \textbf{B}_s(x)=x_s\textbf{A}-x^s\textbf{I}, \end{aligned}$$

and according to Lemma 1 we have

$$\begin{aligned} \textbf{B}_s(x)= \begin{pmatrix} x_s-x^s& \quad 0& \quad 0& \quad \cdots & \quad 0 \\ x_s& \quad x_s-x^s& \quad 0& \quad \cdots & \quad 0 \\ x_s& \quad x_s& \quad x_s-x^s& \quad \cdots & \quad 0 \\ \vdots & \quad \vdots & \quad \vdots & \quad \ddots & \quad \vdots \\ x_s& \quad x_s& \quad x_s& \quad \cdots & \quad x_s-x^s \end{pmatrix}. \end{aligned}$$

Obviously, $x_s=(x^s-1)/(x-1)$, further

$$\begin{aligned} p(x)=\det (\textbf{B}_s(x))=(x_s-x^s)^k. \end{aligned}$$

Consequently, the zeros of the characteristic polynomial p(x) in this particular case coincide to the zeros of $d(x)=x^s-x_s=x^s-x^{s-1}-\cdots -x-1$. Note that this polynomial is the characteristic polynomial of the s-generalized Fibonacci sequence. It is known that d(x) is a Pisot polynomial possessing single zeros. Thus, each zero of $p(x)=(d(x))^k$ has multiplicity k. We record the result we have proved, this is the principal statement of this paper. $\square$

Hence, we have the characteristic polynomial p(x), and it implies the recursive rule for $T_{k,s}(n)$ in direct manner (in n). We illustrate it for small values of k in the next two subsections.

2.1 Example: Two-Color-Tilings ($k=2$)

Consider now the case $k=2$, i.e., we have only two colors.

Then

$$\begin{aligned} \textbf{A}_1=\textbf{A}_2=\cdots = \textbf{A}_s= \begin{pmatrix} 1& \quad 0 \\ 1& \quad 1 \end{pmatrix}, \end{aligned}$$

and $p(x)=\det (\textbf{B}_s(x))=(x_s-x^s)^2$. We can easily have

$$\begin{aligned} p(x)= & \left( \frac{x^s-1}{x-1}-x^s\right) ^2\\= & \frac{(-x^{s+1}+2x^s-1)^2}{(x-1)^2}\\= & \frac{x^{2s+2}-4x^{2s+1}+4x^{2s}+2x^{s+1}-4x^s+1}{(x-1)^2}. \end{aligned}$$

To compute the coefficients of the polynomial, p(x) we apply Horner’s method¹. For simplicity, let $p_a(x)=(x-1)^2p(x)$ and $p_b(x)=(x-1)p(x)$ be introduced.

First, we copy the coefficients of $p_a(x)=x^{2s+2}-4x^{2s+1}+4x^{2s}+2x^{s+1}-4x^s+1$ into the first row of Table 1. Then, following Horners’s scheme, we calculate the quotient polynomial $p_a(x)/(x-1)=p_b(x)$. The coefficients of $p_b(x)$ appear in the second row of the table. Then we divide this result again by $x-1$, and the coefficient of p(x) can be seen in the last row of the table. For technical reason, we assume that $s\ge 3$. For $s=1$ and $s=2$ one can derive $\det (\textbf{B}_k(x))$ separately, the result is $p(x)=(x-1)^2=x^2-2x+1$, and $p(x)=(1+x-x^2)^2=x^4-2x^3-x^2+2x+1$, respectively.

After the program described in the previous paragraph, we turn our attention to the details. In the first row, looking at $x^{2s+2}-4x^{2s+1}+4x^{2s}+2x^{s+1}-4x^s+1$, there are two blocks of zeros according to the zero coefficients of the polynomial. The first block contains $s-2$ zeros, the second one does $s-1$ zeros (see the first row of Table 1). At the beginning of the second row, value 1 indicates that we look for the polynomial evaluation of $p_a(x)$ at 1. Since it is zero, we obtain the coefficients of the polynomial $p_b(x)=p_a(x)/(x-1)$ in the second row. The second element (which is 1 again) is only a copy of the leading coefficient 1 of $x^{2s+2}-4x^{2s+1}+4x^{2s}+2x^{s+1}-4x^s+1$. For other cells of the second row, we use elementary steps explained in the footnote. They give $-3=1\cdot 1+(-4)$, then $1=1\cdot (-3)+4$, then $1=1\cdot 1+0$, etc. This way we obtain gradually the coefficients of $(x-1)p(x)$ in the second row. The third row can be found similarly, it gives the coefficients of p(x). Thus, it follows for $s\ge 3$ that we have

$$\begin{aligned} p(x)=x^{2s}-2x^{2s-1}-x^{2s-2}+\sum _{j=0}^{s-3}jx^{2s-3-j}+\sum _{j=0}^{s-1}(s-j)x^{s-1-j}, \end{aligned}$$

(4)

see Table 1.

Table 1 Horner’s scheme for two colors

The determinant implies immediately the recursive rule for the sequences $(c_i(n))$ ($i=1,2$), as well as the number $T_{2,s}(n)$ of different tilings, as follows. For our convenience, put ${\tau }_{s}(n)=T_{2,s}(n)$. For $n\ge 2s$, from (4) we find the recurrence

$$\begin{aligned} {\tau }_{s}(n)=2{\tau }_{s}(n-1)+{\tau }_{s}(n-2){-}\sum _{j=0}^{s-3}j{\tau }_{s}(n-3-j){-}\sum _{j=0}^{s-1}(s{-}j){\tau }_{s}(n-s-1-j). \end{aligned}$$

Clearly, we need the initial values ${\tau }_{s}(0), {\tau }_{s}(1),\dots ,$ ${\tau }_{s}(2s-1)$ in order to fix the sequence $({\tau }_{s}(n))$ completely.

As an illustration we give the cases $1\le s\le 4$ here:

$$\begin{aligned} \begin{aligned}&{\tau }_{1}(n) =2 {\tau }_{1}(n-1)-{\tau }_{1}(n-2),&(n\ge 2),\\&{\tau }_{2}(n) =2 {\tau }_{2}(n-1)+{\tau }_{2}(n-2) -2{\tau }_{2}(n-3) -{\tau }_{2}(n-4),&(n\ge 4), \\&{\tau }_{3}(n) =2 {\tau }_{3}(n-1)+{\tau }_{3}(n-2)-3{\tau }_{3}(n-4) -2{\tau }_{3}(n-5)-{\tau }_{3}(n-6),&(n\ge 6). \\&{\tau }_{4}(n) =2 {\tau }_{3}(n-1)+{\tau }_{3}(n-2)-{\tau }_{3}(n-4) -4{\tau }_{3}(n-5)-3{\tau }_{3}(n-6) \\&\hspace{6.5cm}-2{\tau }_{3}(n-7)-{\tau }_{3}(n-8),&(n\ge 8). \end{aligned} \end{aligned}$$

The initial values are ${\tau }_{s}(0)=1$ and ${\tau }_{s}(1)=2$ from (1), and for $n\ge 2$ we use again (1) and consider Fig. 1 restricted only to two colors (or see [11]). For the further n and s, Eq. (5) of Theorem 2 provides the initial values later, as we will see in Sect. 2.3. For our convenience, we computed the first few terms of sequences $(\tau _{s}(n))$ in the cases $1\le s\le 4$:

$$\begin{aligned} ({\tau }_{1}(n))_{n\ge 0}&= (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, \ldots ),\\ ({\tau }_{2}(n))_{n\ge 0}&= (1, 2, 5, 10, 20, 38, 71, 130, 235, 420, 744, 1308, 2285, \ldots ),\\ ({\tau }_{3}(n))_{n\ge 0}&= (1, 2, 5, 12, 26, 56, 118, 244, 499, 1010, 2027, 4040, 8004, \ldots ),\\ ({\tau }_{4}(n))_{n\ge 0}&= (1, 2, 5, 12, 28, 62, 136, 294, 628, 1328, 2787, 5810, 12043, \ldots ). \end{aligned}$$

They appear in OEIS [2] as A000027, A001629, A073778, A118898, respectively. (The corresponding sequences are not in OEIS for larger integer s.) Moreover, the rows of Table 2 show the coefficients of the recurrence relations for $s=1,2,\dots ,7$. We note that this result is compatible with the arguments of Ref. [11].

Table 2 Coefficients of the recurrence relations $\tau _s(n)=T_{2,s}(n)$

2.2 Example: Three-Color Tiling ($k=3$)

The equivalent computation to the previous subsection works with

$$\begin{aligned} \begin{aligned} p(x)&=\left( \frac{x^s-1}{x-1}-x^s\right) ^3 \\&=\frac{-x^{3s+3}+6x^{3s+2}-12x^{3s+1}+8x^{3s}-3x^{2s+2}+12x^{2s+1}-12x^{2s}-3x^{s+1}+6x^s-1}{(x-1)^3}. \end{aligned} \end{aligned}$$

The three-step consecutive application of Horner’s scheme provides $p(x)=\sum _{i=1}^3p_i(x)$, where

$$\begin{aligned} \begin{aligned} p_1(x)&=-x^{3s}+3x^{3s-1}-2x^{3s-3}+\sum _{j=1}^{s-3}\frac{j^2-3j-4}{2}x^{3s-3-j},\\ p_2(x)&=\frac{s^2-7s}{2}x^{2s-1}+\frac{s^2-5s+6}{2}x^{2s-2}+\frac{s^2-3s+8}{2}x^{2s-3} \\&\quad +\sum _{j=1}^{s-2}\left( \frac{s^2-3s+8}{2}+j(s-j)\right) x^{2s-3-j}, \\ p_3(x)&=\frac{s^2-s}{2}x^{s-2}+\frac{s^2-3s+2}{2}x^{s-3}\\ &\quad +\sum _{j=1}^{s-3}\left( \frac{s^2-3s+2}{2}+\frac{j(j-2s+3)}{2}\right) x^{3s-3-j}. \end{aligned} \end{aligned}$$

The characteristic polynomial immediately implies the corresponding recurrence rule. For example, in case of $s=2$ it follows that

$$\begin{aligned} T_{3,2}(n)=3T_{3,2}(n-1)-5T_{3,2}(n-3)+3T_{3,2}(n-5)+T_{3,2}(n-6). \end{aligned}$$

Note that the method based on the application of Horner’s scheme would work theoretically if k is larger, but the technical execution would become more and more complicated as k is increasing. On the other hand, the formulae we obtain would not be attractive.

2.3 A General Convolution Result

Let $\widetilde{F}^{(s)}_{n}={F}^{(s)}_{n+s-1}$ denote the nth term ($n\ge 0$) of the shifted non-zero s-generated Fibonacci sequence.

Theorem 2

The sequence $(T_{k,s}(n))_{n=0}^\infty$ is the k-order self-convolution of the non zero s-generated Fibonacci sequence. More precisely, for all $n,k,s\ge 0$ we have

$$\begin{aligned} T_{k,s}(n)= \sum _{\ell _1+\ell _2+\cdots + \ell _k=n} \widetilde{F}^{(s)}_{\ell _1} \widetilde{F}^{(s)}_{\ell _2} \cdots \widetilde{F}^{(s)}_{\ell _k} = \sum _{\ell =0}^{n} T_{k-1,s}(\ell ) \widetilde{F}^{(s)}_{n-\ell }. \end{aligned}$$

(5)

Proof

In the virtue of the tiling conditions the colored dominoes in a tiling are separated from left to right according to the preference order of the colors. Let ${\ell }_i$ be the length of the $C_i$-colored sub-tiling, where $0\le {\ell }_i \le n$ and $\sum _{i=1}^{k} {\ell }_i =n$. Figure 2 illustrates the scheme of such a possible tiling. Clearly, the ith sub-board can be tiled $\widetilde{F}^{(s)}_{\ell _i}$ different ways, and their product enumerates the number of tilings with fixed color separation. Considering all the possible values of ${\ell }_i$’s we obtain $T_{k,s}(n)$ as a sum of the corresponding products. Hence, (5) is valid.

Fig. 2

A dominoe tiling with k colors

2.4 Binary Strings and Tilings

If we consider the unicolored tilings, for example, with grey color, then we can give a one-to-one correspondence between $(1\times n)$–tilings and the binary bit strings of length $n-1$ with no block of s or more 0’s. The base of the bijection is what follows. Imagine a $(1\times n)$ square grid behind the tiling, where neighbor squares are separated from each other by vertical edges. If such an edge is covered by the tiling, then we write 0 above the edge; otherwise, we write 1. Figure 3 shows a $(1\times 10)$—tiling and its corresponding binary string.

Fig. 3

Tilings with one colored dominoes and binary numbers

Similarly, we can give a bijective connection between the tilings with our conditions and $n-k_a$ long binary strings, where any string has no block of s or more 0’s and all the strings are grouped into $k_a$ blocks with $k-1$ separating signs $\omega$. Here, $k_a$ denotes the number of actual colors used in the tiling. If color $C_i$ is not used in a tiling, then the colors $C_{i-1}$ and $C_{i+1}$ are separated doubly by $\omega \omega$. Figure 4 illustrates a tiling and its corresponding separated binary string when $k=k_a=3$ and $s=3$. The separated binary sting has no sub-sequence 000.

Fig. 4

Tilings and binary codes

3 Future Works and Possibilities for Further Application—New Type of Colored Tilings

As a further area of research, one can investigate tilings, where not only colours have a preference, but also the maximum length of dominoes depends on the colours. In this manner, the system of conditions for tilings is the following.

Condition 1.:

Every domino has a color of $k\ge 1$ different colors from the color set $\{C_1,C_2,\dots , C_k\}$.

Condition 2$^\star$.:

The size of a domino in color $C_m$ with $1\le m\le k$ is one of $1\times \ell$, where $\ell$ and $s_m$ are positive integers with $1\le \ell \le s_m$.

Condition 3.:

In a tiling, there exists a preference of colors, more precisely, color $C_j$ cannot be used before color $C_i$ (from left to right) if $i<j$.

A more general tiling problem is defined by Condition 1–3 and the following additional condition:

Condition 4.:

In a tiling, there exists a preference of dominoes; more precisely, dominoes $1\times j$ cannot be used before dominoes $1\times i$ (from left to right) if $i<j$.