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