Tiling a $2×N$ rectangle with $1×1$ and $2×1$ tiles

Question

A $2×N$ rectangle is to be tiled with $1×1$, $1×2$ and $2×1$ tiles. Prove that there is an $x$ such that the number of possible tilings tends to $kx^N$ as $N$ gets large. Find $x$, to $2$ decimal places.

I tried to solve the problem initially by sketching all the possible tilings for $n=1,2,3,..$ but I realised this isn't a practical way to solve the problem.

Answer 1

I would like to do some drawings here, but it will be a good exercise to do it on your own ^^

I follow what Philcar said: you can model the problem with a linear recursion. If you only can tile with $1\times 2$ and $2\times 1$, you get the classical tiling problem which leads to Fibonacci numbers and is equivalent to $k\phi^N$ with $\phi$ the golden ratio (1.618...). More generally, if you reach a linear recursion for the number of possible tilings, you will end with a $kx^N$ as awaited. Let us do the job for your case now.

Denote by $R_N$ the $2\times N$ rectangle you want to tile, $T_N$ the number of possible tilings with $1\times 1$, $1\times 2$ or $2\times 1$ tiles, and $L_N$ the possible tilings for a $2\times N$ rectangle with a $1\times 1$ tile at the bottom right (it appears naturally in the computations, see below). What can be said about the tilings of $R_N$ for a given $N$? Suppose you have such a tiling, and just look at the bottom right corner (the $1\times 1$ corner placed at $(2, N)$ with matrix notations:

• either you get a $2\times 1$ tile, that is a tile filling the last column. Searching possible ways to fill in the rest is the same as searching tilings for $R_{N-1}$ (the remaining places): so you get $T_{N-1}$ such tilings by definition;
• or you get a $1\times 1$ tile, and you get $L_N$ by definition;
• or you get a $1 \times 2$ tile. We can either get a $1\times 2$ tile above it, in which case you get $T_{N-2}$ possibilities for the remaining rectangle $R_{N-2}$; or one $1\times 1$ tile above it at the upper right corner (which create an "L"), and you get $L_{N-1}$ possibilities by definition.

At last you end up with a twisted linear recursion for $(T_N,L_N)$:

$$ \forall N \in \mathbf{N}, N \geqslant 2, \left\{ \begin{array}{l} T_N = T_{N-1} + T_{N-2} + L_N + L_{N-1} \\ L_N = T_{N-1} + L_{N-1} \end{array} \right. $$

From those two relations, we get $T_{N-1} + L_{N-1} = L_N = T_N - T_{N-2} -L_N$ so that:

$$L_N = \frac{T_N - T_{N-2}}{2}$$

which gives you the sought recursion:

$$T_N = 3T_{N-1} + T_{N-2} -T_{N-3}$$

So the characteristic equation has three distinct solutions (the paradisiac case), which can be explicited and the greater one is about $\mathbf{x=3.21}$ (see here).

Now if you want to determine the constant $k$, you have to write down the general solution as $T_N = k_1x_1^N + k_2x_2^N + kx^N$ ($x_1$ and $x_2$ being the two other solutions, and use the first values of $T_N$ computed by hand ($N=0, 1, 2$ are easy and sufficient) to determine the constants, in particular the relevant $k$ (but here, you have to use the exact solutions).

Answer 2

For each $2\times 1$ column, your choices are determined by how many rows are continuing a previous $1\times 2$ brick. Initially neither row is (call this state ${\mathsf{0}}$). When neither row is, you may place a $2\times 1$ brick (staying in ${\mathsf{0}}$). Also, each row continuing a previous $1\times 2$ brick must be completed, and each row not continuing a previous $1\times 2$ brick may be used to start a $1\times 2$ brick or to place a $1\times 1$ brick. So your choices are: ${\mathsf{0}}\rightarrow {\mathsf{0}}\;(\times 2),{\mathsf{1}}\;(\times 2),{\mathsf{2}}$; ${\mathsf{1}}\rightarrow {\mathsf{0}},{\mathsf{1}}$; and ${\mathsf{2}}\rightarrow {\mathsf{0}}$. Since you start in state ${\mathsf{0}}$, the number of ways to be in each state after $N$ columns is given by: $$ \left(\begin{matrix}2 & 2 & 1\\ 1 & 1 & 0\\ 1 & 0 & 0 \end{matrix}\right)^N\cdot \left(\begin{matrix}1\\ 0\\0 \end{matrix}\right)\sim u_1\lambda_1^N, $$ where $\lambda_1\approx 3.21432$ is the largest eigenvalue of the matrix being raised to the $N$-th power. In particular, the number of ways to close off the rectangle is equal to the number of ways of being back in state $\mathsf{0}$, still asymptotic to a constant times $\lambda_1^N$.