A New Domino Tiling Sequence

Roberto Tauraso Dipartimento di Matematica Università di Roma “Tor Vergata” via della Ricerca Scientifica 00133 Roma, Italy

                   tauraso@mat.uniroma2.it

Abstract

In this short note, we prove that the sequence \underline{A061646} from Neil Sloane’s Online Encyclopedia of Integer Sequences is connected with the number of domino tilings of a holey square.

1 Introduction

J. Bao discusses in [1] the following conjecture due to Edward Early (see also [2]): the number of tilings of a holey square, that is a 2n × 2n square with a hole of size 2m × 2m removed from the center, is 2^{n−m} · k^{2} where k is an odd number which depends on n and m. The conjecture has been proven for m = 1, 2, …, 6 and numerical experiments indicate that it holds for several other values of m. Here we are going to show that the conjecture is verified also for m = n−2 and, perhaps what is more surprising, that the corresponding odd numbers k_{n} give a sequence already contained in Sloane’s Encyclopedia [3], namely \underline{A061646}.

Before proving this result we supply some definitions and notations. The Fibonacci numbers \underline{A000045} are defined as the sequence of integers

f_{0} = 0, f_{1} = 1, and f_{n} = f_{n−1} + f_{n−2} for all n ≥ 2.

We will need Cassini’s formula, one of the most famous Fibonacci identities:

f_{n+1}f_{n−1} − f_{n}^{2} = (−1)^{n} for all n ≥ 1.  (1)

The terms of the sequence \underline{A061646} satisfy the recurrence relation given by

a_{0} = 1, a_{1} = 1, a_{2} = 3, and a_{n} = 2a_{n−1} + 2a_{n−2} − a_{n−3} for all n ≥ 3,

and the corresponding generating function is

A(x) = \frac{1 − x − x^{2}}{(1 + x)(1 − 3x + x^{2})}.

The number a_{n} can be expressed in terms of the Fibonacci numbers, as follows:

a_{n} = f_{n+1}f_{n−1} + f_{n}^{2} = 2f_{n}^{2} + (−1)^{n} for all n ≥ 1.

The second formula is obtained from the first by using (1) and it says that a_{n} is always an odd number. The first 20 values of the sequence a_{n} compared with the Fibonacci numbers are as follows:

\begin{matrix}n & f_{n} & a_{n} \\ 0 & 0 & 1 \\ 1 & 1 & 1 \\ 2 & 1 & 3 \\ 3 & 2 & 7 \\ 4 & 3 & 19 \\ 5 & 5 & 49 \\ 6 & 8 & 129 \\ 7 & 13 & 337 \\ 8 & 21 & 883 \\ 9 & 34 & 2311 \\ 10 & 55 & 6051 \\ 11 & 89 & 15841 \\ 12 & 144 & 41473 \\ 13 & 233 & 108577 \\ 14 & 377 & 284259 \\ 15 & 610 & 744199 \\ 16 & 987 & 1948339 \\ 17 & 1597 & 5100817 \\ 18 & 2584 & 13354113 \\ 19 & 4181 & 34961521 \end{matrix}

2 The Result

Lemma 2.1. For all n, m ≥ 1 the number of domino tilings of the L-grid

n m

is

L_{n,m} = f_{n+1}f_{m} + f_{n}f_{m+1}.  (2)

Moreover, L_{n,n−1} = a_{n} for all n ≥ 2 and

L_{n,n−1}^{2} = L_{n,n}L_{n−1,n−1} + 1.  (3)

Proof. In order to prove (2), we start by covering the lower left corner. We can put there either a horizontal domino or a vertical one and then we can either cut along its smaller side or not. Then we get the following four different configurations:

L_{n,m} = f_{n+1}f_{m} +  0  + f_{n}f_{m+1} +  0

where the number of domino tilings of each configuration has been calculated by recalling that the number of ways to tile a 2 × n rectangle is equal to f_{n+1}.

By (2), the identity (3) is equivalent to

(f_{n+1}f_{n−1} + f_{n}^{2})^{2} = (2f_{n+1}f_{n})(2f_{n−1}f_{n}) + 1 = 4f_{n+1}f_{n−1}f_{n}^{2} + 1,

that is

(f_{n+1}f_{n−1} − f_{n}^{2})^{2} = 1

which holds by Cassini’s formula (1).

Finally we show that, as expected by the previous conjecture, the number of domino tilings of the considered holey square is the product of 2^{2} by the square of an odd number. This odd number belongs to the sequence \underline{A061646}.

Theorem 2.2. For all n ≥ 3 the number of domino tilings of the holey square

n  n

is

H_{n} = 4L_{n,n−1}^{2} = 4a_{n}^{2}.  (4)

Proof. By symmetry, the tilings which have a horizontal domino in the lower left corner are one half of the total number H_{n}:

\frac{1}{2}H_{n} =  +

The first tiling can be continued by covering the upper right corner in these four ways:

L_{n,n−1}^{2}  +  0  +  L_{n,n}L_{n−1,n−1} +  0

On the other hand the second tiling can be completed in only one way:

Therefore

\frac{1}{2}H_{n} = L_{n,n−1}^{2} + L_{n,n}L_{n−1,n−1} + 1

and by (3) we obtain

\frac{1}{2}H_{n} = 2L_{n,n−1}^{2} = 2a_{n}^{2}

which gives us (4).

References

[1] J. Bao, On the number of domino tilings of the rectangular grid, the holey square, and related problems, Final Report, Research Summer Institute at MIT, (1997).

[2] L. Pachter, Combinatorial approaches and conjectures for 2-divisibility problems concerning domino tilings of polyominoes, Electron. J. Comb., 4 (1997), 401–410.

[3] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences. Published electronically at http://www.research.att.com/∼njas/sequences/.

2000 Mathematics Subject Classification: Primary 05B45; Secondary 11B37, 11B39. Keywords: domino tilings, Fibonacci numbers.

(Concerned with sequences \underline{A000045} and \underline{A061646}.)

Received March 26 2004; revised version received April 19 2004. Published in Journal of Integer Sequences, April 27 2004.

Return to Journal of Integer Sequences home page.