## Rectangle tiling

### Task number: 3878

How many ways can you tile a rectangle \( n \times k \) by using tiles \( 1 \times 2 \)?

#### Variant

Solve for \(k=2\).

#### Hint

Denote the number of tilings by \(a_n\), then find a recurrence for \(a_n\) and resolve it with help of a generating function. Set the initial values for \( a_0 \), etc. accordingly.

#### Solution

The tiling of the rectangle \(n\times 2 \) can be obtained either from a tiling of a rectangle of length \( n-1 \) with the last tile being vertical, or from a tiling of a rectangle of length \( n-2 \) with the last two tiles laid horizontally.

We get \(a_n=a_{n-1}+a_{n-2}\), while \(a_1=1\) and \(a_2=2\).

#### Answer

The number of tilings of an \(n\times 2\) rectangle is the \(n\)-th Fibonnaci number \(\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}2\right)^n-\left(\frac{1-\sqrt{5}}2\right)^n\right)\).

#### Variant

And how many different ways of tiling by the same tiles has the rectangle when \(k=3\)?

#### Solution

As in the previous case, we try to convert the tiling of the rectangle to the case with smaller \(n\). The first observation is that \(n\) is even.

The rectangle \( 2 \times 3 \) can be tiled in three ways. For \(k\ge 2\), the rectangle \( 2k \times 3 \) can be tiled in two ways so that it cannot be decomposed into two smaller tiled rectangles of height 3, see the figure.

We get the following recurrence:

\(b_n=3b_{n-2}+2b_{n-4}+2b_{n-6}+…+2b_{0}\), přičemž dodefinujeme \(b_0=1\).

If we subtract the next equation from the previous one:

\(b_{n-2}=3b_{n-4}+2b_{n-6}+…+2b_{0}\),

we get \(b_n-4b_{n-2}+b_{n-4}=0\), which can already be solved like other recurrences.

This charakteristic polynomial has roots \(2\pm\sqrt3\).

From \(b_0=1\) and \(b_2=3\) we get a linear combination of powers of roots with coefficients \(\frac12\pm\frac{\sqrt3}6\).

#### Answer

The number of tilings of the rectangle \( n \times 3 \) for an even \( n \) is equal to \(\left(\frac12+\frac{\sqrt3}6\right)\left(2+\sqrt3\right)^{\frac{n}2}+ \left(\frac12-\frac{\sqrt3}6\right)\left(2-\sqrt3\right)^{\frac{n}2}\).

For odd \( n \) such a rectangle cannot be tiled.