1
$\begingroup$

I'm working on a homework assignment involving recursion and I'm having trouble finding an easy way to determine the initial conditions. Heres the problem:

We want to tile ann×1 strip with tiles of three types: 1×1 tiles that are dark-blue, light-blue,and red; 2×1 green tiles, and 3×1 sky-blue tiles. Now give a formula with initial conditions for the number of tilings, considering that blue tiles cannot be next to each other.

I can understand that the recurrence equation is:

$B_n = B_{n-1}+3B_{n-2}+2B_{n-3}+B_{n-4}+B_{n-5}$

And I've found initial conditions for

$B_0=1$ $B_1 = 3$ $B_2 = 6$ $B_3 = 17$

However, I found these but actually writing down all the possible combinations of tiles, but $B_4$ is a huge possible list. Is there some method of combinatorics or permutations I can use to find the initial conditions for $B_4$?

$\endgroup$
  • $\begingroup$ If I let $B_0 = 0$ then I don't understand how the recurrence equation can give me the right answer. If I let $B_0 = 1$ then the method you stated earlier works. At least for what I found $B_{1-3}$ to be. $\endgroup$ – Thedv8ed1 Feb 15 at 17:32
  • 1
    $\begingroup$ Consider separate counts for those that start with blue and those that don’t. That will yield two coupled recurrence relations with fewer initial conditions. You can then derive a recurrence relation for the sum. $\endgroup$ – RobPratt Feb 15 at 18:01
  • 1
    $\begingroup$ My earlier comments have been very confused, so I'm deleting them, and replacing them with this. You can use the same method to find the initial conditions that you did to find the recurrence. You can just set $B_0=1$ and $B_n=0$ for $n<0$ and use the recurrence you already have. $\endgroup$ – saulspatz Feb 15 at 18:03
1
$\begingroup$

Let $a_n$ and $b_n$ the number of $n$-tilings that start with red or green, and blue, respectively. Also, let $c_n$ (your $B_n$) be the total number of $n$-tilings. Then $a_0=a_1=b_0=c_0=1$, $b_1=b_2=2$, $c_1=3$, and, by conditioning on the next tile, we see that \begin{align} a_n &= c_{n-1} + c_{n-2} &&\text{for $n \ge 2$}\\ b_n &= 2 a_{n-1} + a_{n-3} &&\text{for $n \ge 3$}\\ c_n &= a_n+b_n-[n=0] &&\text{for $n \ge 0$} \end{align} Hence \begin{align} c_n &= c_{n-1} + c_{n-2}+2 a_{n-1} + a_{n-3}\\ &=c_{n-1} + c_{n-2}+2 (c_{n-2} + c_{n-3}) + (c_{n-4} + c_{n-5})\\ &=c_{n-1} + 3c_{n-2}+2 c_{n-3} + c_{n-4} + c_{n-5}, \end{align} as you had claimed.


We can also obtain generating functions as follows. Let $A(z)=\sum_{n=0}^\infty a_n z^n$, $B(z)=\sum_{n=0}^\infty b_n z^n$, and $C(z)=\sum_{n=0}^\infty c_n z^n$. Then the recurrence relations imply \begin{align} A(z)-1 - z &=z (C(z)-1) + z^2 C(z) \\ B(z)-1 -2 z-2 z^2 &= 2z (A(z)-1-z) + z^3 A(z) \\ C(z) &= A(z)+B(z)-1 \end{align} Solving for $A(z)$, $B(z)$, and $C(z)$ yields \begin{align} A(z) &= \frac{1}{1 - z - 3 z^2 - 2 z^3 - z^4 - z^5}\\ B(z) &= \frac{1 + z - 3 z^2 - z^3 - z^4 - z^5}{1 - z - 3 z^2 - 2 z^3 - z^4 - z^5}\\ C(z) &= \frac{1 + 2 z + z^3}{1 - z - 3 z^2 - 2 z^3 - z^4 - z^5} \end{align} Notice that the (common) denominator implies that each sequence satisfies the order-5 recurrence $$f_n - f_{n-1} - 3 f_{n-2} - 2 f_{n-3} - f_{n-4} - f_{n-5} = 0,$$ as before. Expanding the series for $C(z)$ yields $$1 + 3 z + 6 z^2 + 18 z^3 + 43 z^4 + 113 z^5 + 287 z^6 + 736 z^7 + 1884 z^8 + 4822 z^9 + 12346 z^{10} + \dots .$$ In particular, $c_3 = 18$, which you could also have obtained directly from the recurrence relations as follows: \begin{align} a_2 &= c_1 + c_0 = 3 + 1 = 4\\ c_2 &= a_2 + b_2 = 4 + 2 = 6\\ a_3 &= c_2 + c_1 = 6 + 3 = 9\\ b_3 &= 2a_2 + a_0 = 2\cdot 4 + 1 = 9\\ c_3 &= a_3+b_3=9+9 = 18 \end{align}

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Wouldn't $B_3$ be $18$ and not $17$?

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Why would it be 18? $\endgroup$ – Thedv8ed1 Feb 18 at 0:55

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.