0

Find a recurrence relation for number of ways to lay out a walkway with tiles if tiles are red,green or grey so that no two red tiles are adjacent and tiles of the same colour are considered indistinguishable.

Why is my method wrong?
Let $a_n$ be the number of ways to lay out a walkway of length $n$ such that no two red tiles are adjacent.

Case 1: Let the first tile be red; so then there are $n-1$ tiles to lay. Thus, the number of layouts after a red starting tile is $a_{n-1}$
Similarly for the green and grey tiles.
Case 2: Let the first tile be red then green/grey; then there are $a_{n-2}$ ways to have a layout without two adjacent red tiles.
Case 3: Let the first tile be grey/green and then red; then there are also $a_{n-2}$ ways.

So total is $a_n = 3\times a_{n-1} + 2\times a_{n-2} + 2\times a_{n-2}$.

similarityinvariance1
  • 313
  • If it starts with a green, then what follows is any of the $a_{n-1}$ ways to lay $n-1$ tiles. Similarly if it starts with a grey. We have then accounted for all of the ways to start with a green or grey, we do not need to account for what happens if it is a green followed by a red or like you are doing in your case 3. Don't overcount these! Now... if it starts with a red, what follows is not just any arrangement of $n-1$ tiles, because if we were to allow any arrangement, we might be putting down an arrangement that started with a red, thus having two reds in a row. – JMoravitz Oct 14 '17 at 05:05
  • If you prefer wording in terms of cases: exactly one of the following cases will occur: 1) Red followed by green (followed by any length n-2) 2) Red followed by grey (followed by any length n-2) 3) Green (followed by any length n-1) 4) Grey (followed by any length n-1). In your cases that you proposed you have overlap between cases. That cannot happen. – JMoravitz Oct 14 '17 at 05:08

2 Answers2

0

Your mistake is in Case 1.

  • The $n^{th}$ tile is either green or grey. $\Rightarrow 2\times a_{n-1}$

  • The $n^{th}$ tile is red. Thus, the $(n-1)^{th}$ tile is either green or grey. $\Rightarrow 2\times a_{n-2}$

$$\bbox[5px,border:2px solid #C0A000]{a_{n} = 2\times a_{n-1} + 2\times a_{n-2}}$$

Hasan Heydari
  • 1,187
  • 1
  • 8
  • 22
0

First, you case 1 is not correct. If you start with a red tile, not all $a_{n-1}$ walkways of length $n-1$ can be appended because you can't use any that also start with a red tile. Second, your case 2 includes the cases from case 1, so they are double counted. Third, you have missed all the cases where the first two tiles are green or gray. Your case 2 is a correct start because any $n-2$ walkway can be appended to red/green or red/gray. In case 3 you can append any $n-1$ walkway to a single green or gray tile, so the recurrence is $$a_n=2a_{n-2}+2a_{n-1}$$

Ross Millikan
  • 374,822