Rosen Ex.6.1

Question

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

Answer 1

We assume that the walkway is one tile in width and n tiles long, from start to finish. Let an be the number of ways to lay out a walkway with n tiles. Consider that the first tile is green, then there are an−1 ways to lay out the remaining walkway with n − 1 tiles without adjacent red tiles. Also, if the first tile is gray, then it also follows that there are an−1 ways to lay out the remaining walkway with n − 1 tiles. We can also consider the first tile is red followed by a green tile, then there are an−2 ways to lay out the remaining walkway with n − 2 tiles. Continuing from before, red followed by gray would also leave us to lay out the rest of the walkway with n − 2 tiles. This would mean that our recurrence relation is an = an−1 + an−1 + an−2 + an−2. Simplified, an = 2an−1 + 2an−2, for n ≥ 2.

 

See For Reference:-http://courses.ics.hawaii.edu/ReviewICS241/morea/counting/RecurrenceRelations-QA.pdf  8.1 pg.512#27

Comments

I have already visited that link, my doubt is we have checked red followed by green, red followed by gray but we have not checked green followed by red and gray followed by red, I think they should be the separate cases...Right??

---

No, they are not separate cases

they are already considered

because, green can be followed by anything red or gray

It can do it in $a_{n-1}$ ways