[Solved]: Why do these recurrences determine the number of ways of tiling a 3xN rectangle with 2x1 dominoes?

Problem Detail: 

http://www.algorithmist.com/index.php/UVa_10918

The above link is a solution to UVa 10918 Problem. The problem is based on Dynamic Programming. I am not able to understand this approach to the problem. I have coded the solution but the approach is completely different. I want to understand the given approach. The problem is:

Determine in how many ways can a 3xN rectangle be completely tiled with 2x1 dominoes.

I only want to know how these recurrence relations came:

f(n)=f(n-2)+2*g(n-1) g(n)=f(n-1)+g(n-2) 

where f(n)=number of tilings of a 3xN rectangle g(n)= number of tilings of a 3xN rectangle with one of its corner squares removed

Asked By : Temp Id

Answered By : Yuval Filmus

Suppose that the rectangle to be tiled has 3 rows and $n$ columns. Consider a tiling of this rectangle using 2$\times$1 dominos. There are two basic options:

1. All tiles touching the $n$th column are horizontal. There must be 3 of them, and if you remove them, you get a tiling of a rectangle of size $3\times(n-2)$.

2. Exactly one tile touching the $n$th column is vertical. It can either touch the top or the bottom. For each of these two options, if you remove it then you get a tiling of a rectangle of size $3\times (n-1)$ with one corner square added. That square must be tiled by a horizontal tile, after whose removal you are left with a tiling of a $3\times(n-1)$ rectangle with one corner square removed.

This explains the formula $f(n) = f(n-2) + 2g(n-1)$.

The same sort of analysis yields the formula for $g(n)$, but I leave that one for you.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/42170