Number of ways to fill 3xN tiles with 2 x 1 dominoes (SPOJ: M3TILE)

Question

I've been trying to solve this programming problem, but since I can't figure it out, I found a solution online. but I can't really understand why that solution works either ..

the task is to calculate in how many ways can a 3*n (n >= 0, n is the only input) rectangle be completely filled with 2*1 dominos.

e.g. (red lines represent dominos):

This was what I first drew on a sheet of paper when I read the text, and I saw that there were three possible combinations that a 3*2 rectangle can have, and that if n is odd the solution is 0 because there is no way to fill up the entire rectangle then (one piece will always stay uncovered by a domino).

So I thought the solution was simply 3^n, if n was even, and 0, if n was odd. turns out, I was wrong.

I found a relatively simple solution here:

#include <iostream>

using namespace std;

int main()
{
    int arr[31];

    arr[0]=1;
    arr[1]=0;
    arr[2]=3;
    arr[3]=0;

    for(int i = 4; i < 31; i++) {
        arr[i] = arr[i-2] * 4 - arr[i-4]; //this is the only line i don't get
    }

    int n;

    while(1) {
        cin >> n;

        if(n == -1) {
            break;
        }

        cout << arr[n] << endl;
    }

    return 0;
}

Why does this work?!

Answer 1

Let T(n) be the number of ways one can tile a 3×n board with 2×1 tiles. Also, let P(n) be the number of ways one can tile a 3×n board with one corner removed with 2×1 tiles. Assume n sufficiently large (>= 4).

Then consider how you can start the tiling from the left (or right, doesn't matter).

You can place the tile covering the top left corner in two ways, vertical or horizontal. If you place it vertical, the tile covering the bottom left corner must be placed horizontally, giving a configuration

|
==

That leaves P(n-1) ways to tile the remaining part. If you place it horizontally, you can place the tile covering the bottom left corner either horizontally or vertically. If you place it vertically, you are in the same situation as before, just reflected, and if you place it horizontally, you must place a tile horizontally between them,

==
==
==

leaving you with a 3×(n-2) board to tile. Thus

T(n) = T(n-2) + 2*P(n-1)              (1)

Now, considering the 3×(n-1) board with one removed (already covered) corner (let's assume top left), you can either place a tile vertically below it, giving

=
|

and leaving you with a 3×(n-2) board to tile, or you can place two tiles horizontally below it, giving

=
==
==

and then you have no choice but to place another tile horizontally at the top, leaving you

===
==
==

with a 3×(n-3) board minus a corner,

P(n-1) = T(n-2) + P(n-3)

Adding up,

T(n) = T(n-2) + 2*(T(n-2) + P(n-3))
     = 3*T(n-2) + 2*P(n-3)                            (2)

But, using (1) with n-2 in place of n, we see that

T(n-2) = T(n-4) + 2*P(n-3)

or

2*P(n-3) = T(n-2) - T(n-4)

Inserting that into (2) yields the recurrence

T(n) = 4*T(n-2) - T(n-4)

q.e.d.

Answer 2

Sharing my image tut.Hope it helps .