2
$\begingroup$

Find the recurrence relation and initial conditions for the number of ways to tile a road of length $n$ cm, using blue, red and green tiles such that the length of each blue tile is 2 cm, green one is 1 cm, red one is 3 cm, and green & blue tiles must not be adjacent.

Hey all. So I defined $a_n$- The requested solution. $b_n$- number of ways such that the first tile is not blue. $c_n$- number of ways such that the first tile is not green. I would like to find the recurrence relation using these definitions, but am quite clueless on how to continue from here. Thanks in advance :)

$\endgroup$
3
$\begingroup$

Let $a_n$ denote the number of ways to tile a road of length $n$ cm. If $r_n$, $b_n$ and $g_n$ denotes the number of ways to tile the road of length $n$ cm starting with a red, blue and green tile respectively, then $$a_n=r_n+b_n+g_n.$$ Now if tiling starts with a red tile, then the remaining tiling is such that it is of length $n-3$ and no blue or green tiles are adjacent. So $$r_n=a_{n-3}.$$

If tiling starts with a green tile, then the second tile cannot be a blue tile so the remaining tiling is of length $n-1$ that starts either with a red or a green tile and therefore $$g_n=r_{n-1}+g_{n-1}=a_{n-4}+g_{n-1}=a_{n-4}+a_{n-5}+g_{n-2}.$$

If tiling starts with a blue tile, then the second tile cannot be a green tile so the remaining tiling is of length $n-2$ that starts either with a red or a blue tile and therefore $$b_n=r_{n-2}+b_{n-2}=a_{n-5}+b_{n-2}.$$ Hence $$a_n=a_{n-3}+a_{n-4}+2a_{n-5}+b_{n-2}+g_{n-2}=a_{n-3}+a_{n-4}+2a_{n-5}+a_{n-2}-r_{n-2}=a_{n-3}+a_{n-4}+2a_{n-5}+a_{n-2}-a_{n-5}=a_{n-2}+a_{n-3}+a_{n-4}+a_{n-5}.$$

$\endgroup$

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.