Tiling problem : Number of ways a floor can be tiled

Question

Find number of ways a floor n meter length and 11 meter wide can be floored with tiles of 2 cm length and 1 cm wide wide tiles without breaking the tiles (assume n is even)

Could you please help in solving this?

Answer 1

The dimensions of the floor ($N$ meter x $11$ meter) are way too large compared to the size of the tiles ($2$ cm x $1$ cm). This corresponds to $N * 55000$ tiles. If we make the crude estimate that every tile can be either horizontally or vertically oriented, you get a number of the order of $2^{N*55000}$.

Clearly, the OP should reduce the dimensions of the floor by several orders of magnitude. In fact I would recommend to start with the smallest possible floors, say $M$ cm x $N$ cm. For these it is straightforward to explore the different patterns and to count their number. It is quite possible that a pattern emerges in the number of solutions as a function of $M$ and $N$.

For $M = 1$ there is only pattern possible: all tiles vertical.

For $M = 2$ we can derive the recurrence relation $n(M,N) = n(M,N-1) + n(M, N-2)$. With initial values $n(2,1) = 1$ and $n(2,2) = 2$. This results in a well-known Fibonacci series.