1
$\begingroup$

Suppose you are trying to tile a 1 x n walkway with 4 different types of tiles: a red 1 x 1 tile, a blue 1 x 1 tile, a white 1 x 1 tile, and a black 2 x 1 tile

a. Set up and explain a recurrence relation for the number of different tilings for a sidewalk of length n.

b. What is the solution of this recurrence relation?

c. How long must the walkway be in order have more than 1000 different tiling possibilities?

This is a problem on my test review and I have no idea how to approach it. We did a similar example in class but only using 1x1 tiles that were all the same (no separate tile colors or sizes). Any help/hints would be appreciated. Thanks in advance!

My initial thought is something along the lines of finding all the ways to use the 1 x 1 tiles then multiplying that by 3 to consider each color variant (don't know how the 2x1 factors in to this though).

$\endgroup$
  • $\begingroup$ Consider the four possibilities for the first 1 by 1 tile and thus set up the recurrence. $\endgroup$ – Aravind Sep 29 '15 at 18:55
  • $\begingroup$ Let $a_n$ be the number of ways to tile a walkway of length $n$. Note that $a_1=3$ and $a_2=10$. Let $n\ge 2$. Can you show that $a_n=3a_{n-1}+a_{n-2}$? Can you then solve this recurrence? $\endgroup$ – André Nicolas Sep 29 '15 at 19:08
4
$\begingroup$

Suppose you have a tiling of length $n+2$. This can be built from:

  • a tiling of length $n+1$ followed by a single tile; OR
  • a tiling of length $n$ followed by a double tile

Let $T_n$ be the number of different ways of tiling a $1\times n$ space. Then for $n\ge1$

$$T_{n+2}=T_{n+1}T_1+T_n=3T_{n+1}+T_n \tag{1}$$

and for the "base" cases: $T_1=3,\:T_2=10$. Then by (1)

$$\begin{array}{l} T_3=33 \\ T_4=109 \\ T_5=360 \\ T_6=1189 \end{array}$$

So the hallway must be at least six units long for 1000+ different tiling possibilities.


The recursion is Fibonacci-like and can be written in matrix form as:

$$\begin{bmatrix}T_{n+2}\\T_{n+1}\end{bmatrix}=\begin{bmatrix}3 & 1\\1 & 0\end{bmatrix}\begin{bmatrix}T_{n+1}\\T_{n}\end{bmatrix}$$

from which the characteristic equation is $(3-\lambda)(-\lambda)-1\times1=0 \implies \lambda^2-3\lambda-1=0$ which has solutions $\lambda=\frac{3\pm\sqrt{13}}{2}$

So we seek a formula for $T_n$ of the form $T_n=a\left(\frac{3+\sqrt{13}}{2}\right)^n+b\left(\frac{3-\sqrt{13}}{2}\right)^n$. Substituting for some values of $T_n$, e.g. $T_3,T_4$ to be safe, you can solve to get

$$T_n=\frac{1}{\sqrt{13}}\left\{\left(\frac{3+\sqrt{13}}{2}\right)^{n+1}-\left(\frac{3-\sqrt{13}}{2}\right)^{n+1}\right\}$$

It turns out that this formula works for $n=1,2$ as well even though the recursion didn't cover these cases. The formula can be proven by induction.


Appendix - Obtaining a Closed-Form Solution

In the formula $T_n=a\left(\frac{3+\sqrt{13}}{2}\right)^n+b\left(\frac{3-\sqrt{13}}{2}\right)^n$ let $a=a_1+a_2\sqrt{13},\:b=b_1+b_2\sqrt{13}$ (with $a_1,a_2,b_1,b_2$ all rational numbers). Then from $T_1=3,T_2=10$ we get:

$$\begin{align} T_1&=(a_1+a_2\sqrt{13})\left(\frac{3+\sqrt{13}}{2}\right)^1+(b_1+b_2\sqrt{13})\left(\frac{3-\sqrt{13}}{2}\right)^1&=3 \\ T_2&=(a_1+a_2\sqrt{13})\left(\frac{3+\sqrt{13}}{2}\right)^2+(b_1+b_2\sqrt{13})\left(\frac{3-\sqrt{13}}{2}\right)^2&=10 \end{align}$$

and from this (by equating rational multiples of $1,\sqrt{13}$) we obtain four simultaneous equations:

$$\begin{array}{rccccccccc} T_1[1]: & 3a_1 &+ &13a_2 &+ &3b_1 &- &13b_2 &= &6 \\ T_1[\sqrt{13}]: & a_1 &+ &3a_2 &- &b_1 &+ &3b_2 &= &0 \\ T_2[1]: & 11a_1 &+ &39a_2 &+ &11b_1 &- &39b_2 &= &20 \\ T_1[\sqrt{13}]: & 3a_1 &+ &11a_2 &- &3b_1 &+ &11b_2 &= &0 \\ \end{array}$$

with solution $a_1=b_1=\frac{1}{2},\:a_2=\frac{3}{26},b_2=-\frac{3}{26}$. So with a little manipulation

$$\begin{align} T_n&=\tfrac{1}{2}(1+\tfrac{3}{13}\sqrt{13})\left(\frac{3+\sqrt{13}}{2}\right)^n + \tfrac{1}{2}(1-\tfrac{3}{13}\sqrt{13})\left(\frac{3-\sqrt{13}}{2}\right)^n \\[2ex] &=\frac{1}{\sqrt{13}}\left(\frac{\sqrt{13}+3}{2}\right)\left(\frac{3+\sqrt{13}}{2}\right)^n + \frac{1}{\sqrt{13}}\left(\frac{\sqrt{13}-3}{2}\right)\left(\frac{3-\sqrt{13}}{2}\right)^n \\[2ex] &=\frac{1}{\sqrt{13}}\left\{\left(\frac{3+\sqrt{13}}{2}\right)^{n+1}-\left(\frac{3-\sqrt{13}}{2}\right)^{n+1}\right\} \end{align}$$

$\endgroup$
  • $\begingroup$ This follows the example we did in class. I just want to be sure I completely understand. Where you are multiplying Tn+1 by 3 is that to account for the 3 different types of 1 x 1 tiles? Otherwise I am not sure where this takes into account the different colored tiles. $\endgroup$ – D.Peterson Sep 29 '15 at 20:55
  • $\begingroup$ @D.Peterson - that's exactly correct. And patterns are being enumerated from a given end of the walkway to the other, e.g. WRB is different to BRW. $\endgroup$ – Marconius Sep 29 '15 at 22:08
  • $\begingroup$ I'm still a little confused in regards to part b. It asks for the "solution" of the recurrence relation. Would the set of values we find starting at T1 through T6 be consider the solution or is it referring to something else entirely? $\endgroup$ – D.Peterson Sep 29 '15 at 22:19
  • $\begingroup$ Reviewing my notes I believe that solution is referring to a closed form solution. I'm not really sure how to reach that. $\endgroup$ – D.Peterson Sep 30 '15 at 0:05
  • $\begingroup$ @D.Peterson - it's tricky if you want to go to the trouble of diagonalising the matrix via its eigenvectors, etc. It's easier if you assume a form for the solution being a linear combination of powers of the eigenvalues, and then use two different values to solve for the coefficients. Note that $a$ and $b$ will "absorb" inaccurate assumptions such as using the wrong exponents and the like. Or if you compute the powers of either eigenvalue (say $\frac{3+\sqrt{13}}{2}$) you can notice that the $T_n$ show up as coefficients of $\sqrt{13}$. $\endgroup$ – Marconius Sep 30 '15 at 0:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.