Domino Tilings and Products of Fibonacci and Pell Numbers

James A. Sellers

Department of Mathematics The Pennsylvania State University 107 Whitmore Lab University Park, PA 16802

                    sellersj@math.psu.edu

Abstract

In this brief note, we prove a result which was “accidentally” found thanks to Neil Sloane’s Online Encyclopedia of Integer Sequences. Namely, we prove via elementary techniques that the number of domino tilings of the graph W_{4} × P_{n−1} equals f_{n}p_{n}, the product of the n^{th} Fibonacci number and the n^{th} Pell number.

1 Introduction

Recently I received an electronic mail message [1] in which I was notified that a pair of duplicate sequences existed in Neil Sloane’s Online Encyclopedia of Integer Sequences [3]. This involved sequence \underline{A001582} and the former sequence \underline{A003763}. One of these sequences was described as the product of Fibonacci and Pell numbers, while the other was the number of domino tilings of the graph W_{4} × P_{n−1}.

I soon notified Neil Sloane of this fact and he promptly combined the two sequence entries into one entry, \underline{A001582}. Upon combining these two entries, he also noted that it was not officially a theorem (that the product of the Fibonacci and Pell numbers was always equal to the number of domino tilings of W_{4} × P_{n−1}), but that is was “certainly true.”

The primary goal of this short note is to prove this result so that its status is indeed a theorem. We close the paper by noting two other results relating domino tiling sequences in

[2] with Fibonacci numbers.

Before proving the main result, we supply some definitions and notation for the sake of completeness. First, we note that the graph W_{4} is K_{4} − e. Moreover, the graph P_{n} is the path graph on n vertices. The Fibonacci numbers \underline{A000045} are defined as the sequence of integers

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

The Pell numbers \underline{A000129} are defined as the sequence of integers

p_{1} = 1, p_{2} = 2, and p_{n+2} = 2p_{n+1} + p_{n} for all n ≥ 0.  (2)

2 The Results

Theorem 2.1. The number of domino tilings of W_{4} × P_{n−1} equals f_{n}p_{n} for all n ≥ 2. Proof. Thanks to an article of Faase [2, page 146], we know that the number of domino tilings of W_{4} × P_{n−1}, which we will denote by c_{n}, satisfies c_{2} = 2, c_{3} = 10, c_{4} = 36, c_{5} = 145 and

c_{n+4} − 2c_{n+3} − 7c_{n+2} − 2c_{n+1} + c_{n} = 0  (3)

for all n ≥ 2. (This is slightly different than the notation used in Faase, where he defines a function C(n) wherein c_{n} = C(n − 1) and then does all work in terms of C(n) rather than c_{n}.)

It is easy to check that f_{n}p_{n} satisfies the initial conditions above. Hence, we focus on checking that f_{n}p_{n} satisfies (3).

Repeated applications of (1) and (2) yield

f_{n+2} = f_{n} + f_{n+1}, f_{n+3} = f_{n} + 2f_{n+1}, and f_{n+4} = 2f_{n} + 3f_{n+1}  (4)

while

p_{n+2} = p_{n} + 2p_{n+1}, p_{n+3} = 2p_{n} + 5p_{n+1}, and p_{n+4} = 5p_{n} + 12p_{n+1}.  (5)

We now substitute the findings in (4) and (5) into the left-hand side of (3) and simplify:

f_{n+4}p_{n+4} − 2f_{n+3}p_{n+3} − 7f_{n+2}p_{n+2} − 2f_{n+1}p_{n+1} + f_{n}p_{n}
= (2f_{n} + 3f_{n+1})(5p_{n} + 12p_{n+1}) − 2(f_{n} + 2f_{n+1})(2p_{n} + 5p_{n+1}) − 7(f_{n} + f_{n+1})(p_{n} + 2p_{n+1})
−2f_{n+1}p_{n+1} + f_{n}p_{n}
= f_{n}p_{n}(10 − 4 − 7 + 1) + f_{n+1}p_{n}(15 − 8 − 7) + f_{n}p_{n+1}(24 − 10 − 14) + f_{n+1}p_{n+1}(36 − 20 − 14 − 2)
= 0

Thus, c_{n} = f_{n}p_{n} for all n ≥ 2 and the proof is complete.

We note that at least two other domino tiling sequences that appear in [2] are also closely related to Fibonacci numbers.

We first consider sequence \underline{A003775} which appears in [2, p. 147] in relationship to the number of domino tilings of P_{5} × P_{2n}. Based on this sequence, we define d_{1} = 1, d_{2} = 8, d_{3} = 95, d_{4} = 1183 and

d_{n+4} − 15d_{n+3} + 32d_{n+2} − 15d_{n+1} + d_{n} = 0  (6)

for all n ≥ 1. Computational experimentation indicates that f_{2n−1} | d_{n} for several values of n. This leads to the following theorem:

Theorem 2.2. For all n ≥ 1, d_{n} = g_{n}h_{n} where g_{n} is the n^{th} term in the sequence \underline{A004253} and h_{n} = f_{2n−1} for all n ≥ 1.

Remark: Note that \underline{A004253} is related to the number of domino tilings in K_{3} × P_{2n} and S_{4} × P_{2n} as noted by Faase in [2, pp. 146-147]. Moreover, \underline{A004253} is quite similar to \underline{A028475}.

Proof. The proof here follows a similar line of argument to that of Theorem 2.1. From the information given in \underline{A004253}, we know that

g_{1} = 1, g_{2} = 4, and g_{n+2} = 5g_{n+1} − g_{n}.  (7)

Moreover, we have

h_{1} = 1, h_{2} = 2, and h_{n+2} = 3h_{n+1} − h_{n}.  (8)

It is easy to check that d_{n} = g_{n}h_{n} for 1 ≤ n ≤ 4, so we focus our attention on the recurrence (6). We know from (7) that

g_{n+2} = 5g_{n+1} − g_{n}, g_{n+3} = 24g_{n+1} − 5g_{n}, and g_{n+4} = 115g_{n+1} − 24g_{n}  (9)

while (8) yields

h_{n+2} = 3h_{n+1} − h_{n}, h_{n+3} = 8h_{n+1} − 3h_{n}, and h_{n+4} = 21h_{n+1} − 8h_{n}.  (10)

We now substitute the information from (9) and (10) into the left-hand side of (6) and obtain the following:

g_{n+4}h_{n+4} − 15g_{n+3}h_{n+3} + 32g_{n+2}h_{n+2} − 15g_{n+1}h_{n+1} + g_{n}h_{n}
= (115g_{n+1} − 24g_{n})(21h_{n+1} − 8h_{n}) − 15(24g_{n+1} − 5g_{n})(8h_{n+1} − 3h_{n}) + 32(5g_{n+1} − g_{n})(3h_{n+1} − h_{n})
−15g_{n+1}h_{n+1} + g_{n}h_{n}
= g_{n}h_{n}(192 − 225 + 32 + 1) + g_{n+1}h_{n}(−920 + 1080 − 160)
+g_{n}h_{n+1}(−504 + 600 − 96) + g_{n+1}h_{n+1}(2415 − 2880 + 480 − 15)
= 0

This completes the proof.

Finally, we consider the last sequence of values in [2], which is related to the number of domino tilings of P_{8} × P_{n} and appears as \underline{A028470} in [3]. The first 32 values of the sequence are as follows:

\begin{matrix}n & C_{n} \\ 1 & 1 \\ 2 & 34 \\ 3 & 153 \\ 4 & 2245 \\ 5 & 14824 \\ 6 & 167089 \\ 7 & 1292697 \\ 8 & 12988816 \\ 9 & 108435745 \\ 10 & 1031151241 \\ 11 & 8940739824 \\ 12 & 82741005829 \\ 13 & 731164253833 \\ 14 & 6675498237130 \\ 15 & 59554200469113 \\ 16 & 540061286536921 \\ 17 & 4841110033666048 \\ 18 & 43752732573098281 \\ 19 & 393139145126822985 \\ 20 & 3547073578562247994 \\ 21 & 31910388243436817641 \\ 22 & 287665106926232833093 \\ 23 & 2589464895903294456096 \\ 24 & 23333526083922816720025 \\ 25 & 210103825878043857266833 \\ 26 & 1892830605678515060701072 \\ 27 & 17046328120997609883612969 \\ 28 & 153554399246902845860302369 \\ 29 & 1382974514097522648618420280 \\ 30 & 12457255314954679645007780869 \\ 31 & 112199448394764215277422176953 \\ 32 & 1010618564986361239515088848178 \end{matrix}

The recurrence relation satisfied by the values of C_{n} is given by

C_{n+32} = 153C_{n+30} − 7480C_{n+28} + 151623C_{n+26} − 1552087C_{n+24} + 8933976C_{n+22} − 30536233C_{n+20}

+63544113C_{n+18} − 81114784C_{n+16} + 63544113C_{n+14} − 30536233C_{n+12} + 8933976C_{n+10}

−1552087C_{n+8} + 151623C_{n+6} − 7480C_{n+4} + 153C_{n+2} − C_{n}

for all n ≥ 1.

We note that f_{n+1} | C_{n} for several values of n.

\begin{matrix}n & C_{n}/f_{n+1} \\ 1 & 1 \\ 2 & 17 \\ 3 & 51 \\ 4 & 449 \\ 5 & 1853 \\ 6 & 12853 \\ 7 & 61557 \\ 8 & 382024 \\ 9 & 1971559 \\ 10 & 11585969 \\ 11 & 62088471 \\ 12 & 355111613 \\ 13 & 1939427729 \\ 14 & 10943439733 \\ 15 & 60338602299 \\ 16 & 338172377293 \\ 17 & 1873494595072 \\ 18 & 10464657396101 \\ 19 & 58113694771149 \\ 20 & 324052035315389 \\ 21 & 1801727076022631 \\ 22 & 10038214290617749 \\ 23 & 55845947547948897 \\ 24 & 311010011115265801 \\ 25 & 1730773816266538081 \\ 26 & 9636747170211055304 \\ 27 & 53636683818362516979 \\ 28 & 298610928685279993661 \\ 29 & 1662149072277201394907 \\ 30 & 9253169548548380483401 \\ 31 & 51507590702129135617317 \\ 32 & 286734628936105610236201 \\ 33 & 1596133084485272225826727 \\ 34 & 8885301696820653301727657 \\ 35 & 49461269578409945493024768 \\ 36 & 275337533349256635378114713 \\ 37 & 1532712030034359905504838377 \\ 38 & 8532165290411528453455489081 \\ 39 & 47495826004154548026644356683 \\ 40 & 264395102236750242015097270393 \end{matrix}

This leads to the conjecture that f_{n+1} | C_{n} for all n ≥ 1. We leave the proof of this (assuming it is true) to the reader, as the calculations involved herein would be straightforward but tedious.

3 Acknowledgements

The author gratefully acknowledges Frank Ellerman for bringing this problem to his attention and Per Hakan Lundow for valuable e-conversations. The author also thanks the referees for their helpful insights.

References

[1] Personal communication from Frank Ellerman, frank.ellermann@t-online.de, February 9, 2002.

[2] F. J. Faase, On the number of specific spanning subgraphs of the graphs G × P_{n}, Ars Combinatoria, 49 (1998), 129-154.

[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: 11B37, 11B39 Keywords: domino tilings, Fibonacci numbers, Pell numbers

(Concerned with sequences \underline{A000045}, \underline{A000129}, \underline{A001582}, \underline{A003775}, \underline{A004253}, \underline{A028470} and \underline{A028475}.)

Received March 20, 2002; revised version received May 1, 2002. Published in Journal of Integer Sequences May 6, 2002.

Return to Journal of Integer Sequences home page.