# Why do these recurrences determine the number of ways of tiling a 3xN rectangle with 2x1 dominoes?

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

• It is explained on the site. So can you be more explicit as to what you do not understand? – babou May 5 '15 at 14:12
• What have you tried and where did you get stuck? Hint: correctness of recurrences is typically shown by induction (here on $n$). – Raphael May 5 '15 at 15:19

Suppose that the rectangle to be tiled has 3 rows and $$n$$ columns.

□□□...□
□□□...□
□□□...□
123...n


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)$$.

□□□...⧆⧆
□□□...■■
□□□...⧆⧆
123....n

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 added.

□□□...⧇⧇      □□□...□⧆
□□□...□⧆      □□□...□⧆
□□□...□⧆      □□□...⧈⧈
123....n      123.....n

|             |
V             V

□□□...□□     □□□...□
□□□...□      □□□...□
□□□...□      □□□...□□
123....n     123....n


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.

The picture should say more than words.

• But if you need the words, see the answer by @Yuval-Filmus. – Hendrik Jan May 5 '15 at 13:51
• Sorry. As @babou observes above the first link in the question has some explanation and these pictures (albeit as ascii art). So how can they help? – Hendrik Jan May 6 '15 at 23:34