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

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.

• Try to write a linear recursion first by columns, and put it in its matrix form. Perhaps eigenvalues would help there. Oct 7 '16 at 22:59
• It is due to be connected to Fibonacci numbers. Have a look for example at (dartmouth.edu/~academicoutreach/docs/…). Besides, I am surprised by the $1 \times 1$. Isn't it $1 \times 2$ ? Oct 7 '16 at 23:02
• Are you allowed to flip the $2\times 1$ tile? i.e do both $2 \times 1$ and $1\times 2$ tiles allowed? If not, the number of possible tilings is trivial. Oct 7 '16 at 23:42
• Yes you are allowed to flip the tiles
– Hogg
Oct 7 '16 at 23:53
• Yes, you can use $1 \times 1$ tiles, $2 \times1$ tiles, and $1 \times 2$ tiles.
– Hogg
Oct 8 '16 at 0:18

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).

• @Hogg Take you rectangle $R_N$, you want to tile it. We suppose in this third case that there is a $1\times2$ tile at the bottom right corner. Now, what can happen above it, that is at the top right corner ? There is place either to a 1x2 tile (and you get a $R_{N-2}$ rectangle remaining, so $T_{N-2}$ possibilities for tiling the rest), or to a 1x1, in which case the remainder to tile is... A rectangle from which we substracted an L, as in the second bullet point (but with size one less), right ? Draw a picture, and tell me if you see it! Dec 11 '16 at 22:08
• You can either have a $1\times2$ tile directly above it, or two $1\times1$ tiles above it. Also, should it say $T_{N-2},R_{N-2}$ instead of $T_{N-1},R_{N-1}$
– Hogg
Dec 11 '16 at 22:10
• @Hogg No, there is another possibility: On tile 1x1 above it, then a 1x2, it gives an L of size n-2. There is no reason for having a 1x1 tile at the place $(1, N-1)$ if you put a 1x1 at $(1,N)$, you can have something else (in this case a 1x2) Dec 11 '16 at 22:15
• @Hogg We actually discrimine only on what happens on the place $(1,N)$, provided you have the bottom right filled with a tile $1\times 2$. There cannot be a tile $2\times 1$ (not enough place for it, for the place juste below is already filled), hence it remains the two other possibilities : a $1\times 2$ (which gives $T_{N-2}$) and a $1\times 1$ (which gives a $L_{N-1}$). You do not have to understand for the remaining places, it would juste will create more distinctions of cases and more trickier computations: this one suffice. Dec 11 '16 at 22:30
• @Hogg Well, I didn't at first, and I wasn't thinking to need some intermediate quantity like that... but it arose naturally during the computations, I couldn't avoid it... hence I introduced it. It it where the intuition lacks of lucidity and formality allows going further ;) Do you see why when you try ? When you get an "L" (for instance with an 1x1 at the bottom left, you cannot guarantee getting rid of it after one tile more: if you put a 1x2, you get another "L" (smaller, from where we get the idea of finding a recursion relation). Is at least the formal solution satisfying you? Dec 13 '16 at 20:43

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$.

• Thank you for your answer. Could you explain the sentence "So your choices are: $0→0 (×2),1 (×2), 2; 1→0, 1$; and $2→0$".
– Hogg
Dec 31 '16 at 15:07
• Yes. If the state is 0 (neither row in the middle of a horizontal brick), you can place a vertical brick or two little square bricks, leaving the state 0 (in x2 different ways); or you can place one little square brick and one horizontal brick, changing the state to 1 (in x2 different ways, because the little brick can be in either row); or you can place two horizontal bricks, changing the state to 2. ... Jan 5 '17 at 15:32
• ... If the state is 1 (exactly one row in the middle of a horizontal brick), you must complete the horizontal brick, and may place either a little square brick or a new horizontal brick in the other row (causing the state to be 0 or 1, respectively). Finally, if the state is 2 (both rows in the middle of horizontal bricks), you must complete both, taking the state to 0. Jan 5 '17 at 15:33