Paving by using a recurrence relation

Question

I was asked the next question: What is the recurrence relation, $A_n$, of paving an $n$ meters long pavement using three colored floor tiles : yellow,orange,red whereas the yellow is 3 meters long, the orange is 2 meters long and the red is 1 meters long. The rule is that an orange floor tile can't be put alongside a red one.

I wanna know if my answer makes any sense:

Let $C_n$ be the recurrence relation that represents the 'legal' ways to pave a pavement that starts with an orange floor tile

Let $B_n$ be the recurrence relation that represents the 'legal' ways to pave a pavement that starts with a red floor tile

Using the question's 'rules'

$A_n = A_{n-3} + B_n + C_n$

$B_n= A_{n-1} - C_{n-1}$ (All of the legal options minus the ones that start with an orange)

$C_n= A_{n-2} - B_{n-2}$ (All of the legal options minus the ones that start with a red one)

I tried bringing it to an equation that contains only $A_n$ but failed to do so.. Am I doing it right? Does the answer make any sense? Thank you so much for taking the time and reading my question!

Answer 1

Your three relations appear to be correct. One suggestion, though: Denote the number of $n$-meter pavings starting with a Yellow tile by $Y_n$, the number starting with an Orange tile by $O_n$ (instead of $C_n$) and the number starting with a Red tile by $R_n$ (instead of $B_n$). This makes it easier to keep track of which means which (in English, anyway, but you can translate it to your own language). $A_n$ can continue to represent the count of all legal patterns.

Then we have the following relationship:

• Any legal pattern must start with either a yellow, orange, or red tile: $$A_n = Y_n + O_n + R_n$$
• For patterns beginning with a Yellow tile, if you remove the tile, you get a legal pattern for $n-3$ meters. Conversely, any legal pattern for $n-3$ meters becomes a yellow-leading pattern for $n$ meter by adding a yellow tile to the front. So $$Y_n = A_{n-3} = Y_{n-3} + O_{n-3} + R_{n-3}$$
• For Orange-leading patterns, removing the leading orange tile leaves a pattern for $n-2$ meters that cannot begin with a red tile. Conversely, any $n-2$ meter pattern not beginning with a red tile becomes a legal orange-leading $n$ meter pattern by addition of an orange tile to the front. Thus $$O_n = Y_{n-2} + O_{n-2} = A_{n-2} - R_{n-2}$$
• For Red-leading patterns, removing the leading red tile produces a $n-1$ pattern that cannot begin with orange. And adding a red tile to such a pattern reproduces the red-leading pattern, so $$R_n = Y_{n-1} + R_{n-1} = A_{n-1} - O_{n-1}$$

These are the recursion relations you produced (with $Y_n$ replaced by $A_{n-3}$, but I thought it was better to be explicit about why this is done).

While it would be nice to express it as a single recursive formula, such exprssions are not always easy to find. One way you could express it as a single formula is to use matrices:

$$\begin{bmatrix}Y_n\\O_n\\R_n\end{bmatrix} = \begin{bmatrix}0&0&0\\0&0&0\\1&0&1\end{bmatrix}\begin{bmatrix}Y_{n-1}\\O_{n-1}\\R_{n-1}\end{bmatrix}+\begin{bmatrix}0&0&0\\1&1&0\\0&0&0\end{bmatrix}\begin{bmatrix}Y_{n-2}\\O_{n-2}\\R_{n-2}\end{bmatrix}+\begin{bmatrix}1&1&1\\0&0&0\\0&0&0\end{bmatrix}\begin{bmatrix}Y_{n-3}\\O_{n-3}\\R_{n-3}\end{bmatrix}$$ Which you can express symbolically as $$P_n = M_1P_{n-1} + M_2P_{n-2} + M_3P_{n-3}$$where the definitions of $P_n$ and $M_i$ should be obvious. From this form you may be able to develop expressions for the $n$ terms similar to those for one-dimensional recursions.

In any case, the multiple recursion is enough to allow you to start calculating higher values from those for $n = 1, 2, 3$; $$\begin{array}{c|ccc} n & Y_n & O_n & R_n \\ \hline 1& 0& 0& 1\\ 2& 0& 1& 1\\ 3& 1& 0& 1\\ 4& 1& 1& 2\\ 5& 2& 1& 3\\ 6& 2& 2& 5\\ 7& 4& 3& 7\\ 8& 6& 4& 11\\ 9& 9& 7& 17\\ 10& 14& 10& 26\\ 11& 21& 16& 40\\ 12& 33& 24& 61\\ 13& 50& 37& 94\\ 14& 77& 57& 144\\ 15& 118& 87& 221\\ 16& 181&134& 339 \end{array}$$