# UVa 10918

Jump to navigation Jump to search

## Summary

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

## Explanation

It's a typical problem on dynamic programming. One possible solution is described below.

Let ${\displaystyle f(n)}$ be the number of tilings of a 3xN rectangle (which is what we're looking for) and let ${\displaystyle g(n)}$ denote the number of tilings of a 3xN rectangle with one of its corner squares removed.

These functions satisfy the recurrent relations: ${\displaystyle f(n)=f(n-2)+2g(n-1),g(n)=f(n-1)+g(n-2).}$ The formulas can be illustrated as follows:

```********   AA*******   AA******   A*******
******** = BB******* + B******* + A*******
********   CC*******   B*******   BB******
f(n)   =  f(n-2)   +  g(n-1)  +  g(n-1)

********   A********   AA*******
******** = A******** + BB*******
*******    ********    CC******
g(n)   =   f(n-1)  +   g(n-2)
```

The boundary values for the relations are: ${\displaystyle f(0)=1,f(1)=0,g(0)=0,g(1)=1.}$

For any odd value of N, the number of tilings of a 3xN rectangle is 0.

```0
1
2
8
12
30
-1
```

```1
0
3
153
2131
299303201
```