|
|
|
|
|
Domino TilingSuppose we use dominoes measuring 2×1 to tile an infinite strip of height 2. In a typical tiling what fraction of the dominoes will be oriented vertically? Typical can be defined rigorously by considering all possible tilings of a 2×n rectangle and then letting n go to infinity.
Answer: 1/sqrt(5)SolutionLet a(n) be the number of tilings by 2×1 dominoes of a 2×n rectangle, where 2 is the height and n is the width. For convenience, I will refer to this as an "n-tiling". There is one 0-tiling (no dominoes), and one 1-tiling (one vertical domino). Viewed from left to right, an n-tiling, n>1, can begin either with a single vertical domino (|), or a pair of horizontal ones (=). In this way, an n-tiling is a sequence of | and =. The number of n-tilings is the number of n-tilings that begin with | plus the number of n-tilings that begin with =. After placing I first, there are a(n-1) possible tilings, and after placing the = first, there are a(n-2) possible tilings. So a(n)=a(n-1)+a(n-2), and a(n)=F(n+1), where F is the Fibonacci sequence (Sloane's A000045). Let b(n) be the number of vertical dominoes (|) in all a(n) n-tilings. There are a(n-1) tilings that begin with |, plus b(n-1) other |'s in those tilings for a total of a(n-1)+b(n-1) |'s in an n-tiling that begins with |. In addition, there are a(n-2) tilings that begin with =, which together contain b(n-2) |'s. So b(n)=a(n-1)+b(n-1)+b(n-2). Starting at n=0, b is 0, 1, 2, 5, 10, 20, 38, 71, 130, 235, ... (b(n) is given by Sloane's A001629(n+1)). Let c(n) be the number of pairs of horizontal dominoes (=) in all the a(n) tilings. There are a(n-2) tilings that begin with =, plus c(n-2) other ='s in those tilings for a total of a(n-2)+c(n-2) ='s in an n-tiling that begins with =. In addition, there are a(n-1) tilings that begin with |, which together contain c(n-1) ='s. So c(n)=a(n-2)+c(n-1)+c(n-2). Starting at n=0, c is 0, 0, 1, 2, 5, 10, 20, 38, 71, 130, ... the same sequence as b, offset by one place! So c(n)=b(n-1). which looks daunting, but like the closed form of the Fibonacci sequence, the second half of this expression approaches zero, leaving us with And so the ratio b(n+1) / b(n) approaches phi ((1+sqrt(5))/2) as n approaches infinity. Recapa(n) = F(n+1), the Fibonacci sequence, offset by one place, is the number of n-tilings. Since the ratio of successive elements of b approaches phi as n approaches infinity, the fraction of vertical dominoes, which is
approaches phi / (phi+2) = 1/sqrt(5). Internet ReferencesRelated pages in this website
|
|
The webmaster and author of the Math
Help site is Graeme McRae.
|
![\[ b(n) = \frac{1}{5}\left(\left(n+1\right)-\frac{1}{\sqrt{5}}\right)\left(\frac{1+\sqrt{5}}{2}\right)^{n+1} + \frac{1}{5}\left(\left(n+1\right)+\frac{1}{\sqrt{5}}\right)\left(\frac{1-\sqrt{5}}{2}\right)^{n+1}, \]](PuzzleDominoTilingEq1.gif)
![\[ b(n) \approx \frac{1}{5}\left(\left(n+1\right)-\frac{1}{\sqrt{5}}\right)\left(\frac{1+\sqrt{5}}{2}\right)^{n+1} \]](PuzzleDominoTilingEq2.gif)
