TILING RECTANGLES

Suppose you have a rectangular room, NxM meters in size (M even), and you want to tile its floor with 1x2 tiles, but you do not want to have to cut any tile. In how many "different" ways cna you do that? By "different" i mean that two tilings that are obtained one from the other by reflection in one (or both) axis are not different. Furthermore if the room is square, tilings that differ by rotation are also considered the same.

```         N  2    3    4    5    6    7    8    9   10   11
+--------------------------------------------------
M 2 |    1    2    4    5    9   12   21   30   51   76
4 |    4    5   11   33   98  230  658
6 |    9   14   98  329 1712
8 |   21   46  658 3818
10 |   51  156 4876
12 |  127  561
14 |  322
```

The number in the first column are the sequence A005207: f(M) = [ Fib(1+M) + Fib((M+4)/2) ] / 2, where Fib(n) are Fibonacci numbers, Fib(0)=0, Fib(1)=1, and Fib(n)=Fib(n-1)+Fib(n-2). The same sequence occurs at the even positions on the first row, obviously. At the odd position in that row there is another sequence, A051450 also related to Lozanic's triangle, [ Fib(1+N) + Fib((N+1)/2) ] / 2.

Now suppose you want a tiling that has no cut-line from one side of the room to the opposite side. A "cut-line" is a line that does not cross any tile. Apart from the trivial solution with one tile for the 1x2 room, the smallest room that has a solution is 5x6 and it has exactly two different solutions,

```  _ _ ___ ___      _ ___ _ ___
| | |___|___|    | |___| |___|
|_|_| |___| |    |_|___|_| | |
|___|_| | |_|    | | |___|_|_|
| |___|_|_| |    |_|_| |___| |
|_|___|___|_|    |___|_|___|_|
```

How many different solutions exists for a NxM room ?
N 5 6 7 8 9 10 11 12 +---------------------------------------- M 6 | 2 0 32 18 418 415 4545 6461 8 | 28 18 3391 6411 10 | 303 415 12 | 2601 6461

What about other topologies ? Suppose that the room is a toroidal room, ie, opposite sides are identified, what are the numbers of different tilings and different tilings with no cut-line (a cut-line is a great-circle in one of the two axis of the torus) ? A 4x4 torus has a "trivial" solution with no cut-line:

```  ___   _
|___|_| |
| |___|_|
|_| |___|
._|_| |_.
```

Other topologies to play with are the annulus, the moebius strip and the projective plane. Here is a 4x6 annulus (folded on 4)

```  ___ ___ _ _
|___|___| | |
| |___| |_|_|
|_| | |_|___|
._|_|_|___|_.
```

For the topologies with only one-side the cut-lines are defined as going around until they come back to the starting point. So, for example the 5x6 moebius strip folded on 5 has six vertical lines, and two horizontal ones, one between rows a|b which continues between rows d|e to come back at the start point, the other betweenn rows b|c and c|d.

```    ___________
a | |___|___|_    e
b |_| |___|___|   d
c  _|_| |___|_    c
d |___|_| |___|   b
e  _|___|_|___|   a
```

Marco Corvi - 2012