4. In how many different ways can we pave a $3 \times 10$ area with $2 \times 1$ tiles, if the tiles can be placed in both mutually perpendicular directions?
SOLUTION. Instead of the area $3 \times 10$, we consider a general area $3 \times 2n$, where $n$ is a natural number, and denote as $a_{n}$ the number of all ways to tile this area with $2 \times 1$ tiles (of which we need $3n$ pieces). ${ }^{2}$ Although our task is to find only one of the numbers $a_{n}$, namely the number $a_{5}$, the intended generalization is not self-serving. It will turn out that each individual value of $a_{n}$ can be calculated according to a simple formula if we know the two previous values $a_{n-1}$ and $a_{n-2} \cdot{ }^{3}$ Thus, from the "initial" values $a_{1}, a_{2}$, we can first calculate $a_{3}$, then $a_{4}$, and so on up to the desired $a_{n}$. This procedure (common in a series of combinatorial situations, see introductory problems) is called the recursive method or recursion procedure.

While the value $a_{1}=3$ is easy to determine by drawing all possible tilings of the area $3 \times 2$ (Fig. 2), a similar approach to determine the value $a_{2}=11$ would be quite laborious. Instead, we will also introduce numbers $b_{n}$, which will be useful for our further recursive considerations: each number $b_{n}$ will denote the number of all ways to partially tile the area $3 \times (2n-1)$ with $2 \times 1$ tiles in the amount of $3n-2$ pieces, leaving one uncovered $1 \times 1$ square in a specifically chosen corner of the entire area, say the bottom right. Due to axial symmetry, the same number $b_{n}$ of ways will result if the uncovered square is required to remain in the top right corner.
![](https://cdn.mathpix.com/cropped/2024_04_17_7f7149a15f3fd6cbd268g-07.jpg?height=200&width=620&top_left_y=1274&top_left_x=724)

Fig. 2

To the value $a_{1}=3$, we add the obvious value $b_{1}=1$ and proceed to the actual recursive method. In it, we will derive that for every integer $n>1$ the equations

$$
b_{n}=a_{n-1}+b_{n-1} \quad \text { and } \quad a_{n}=a_{n-1}+2 b_{n}
$$

hold.

The first equation in (1) is proven by dividing all tilings of the area $3 \times (2n-1)$ with the "cut out" $1 \times 1$ square in the bottom right into two disjoint groups depending on whether the top right $1 \times 1$ square is covered by a vertical tile (tilings of type A in Fig. 3) or by a horizontal tile (tilings of type B, where the positions of the next two, a total of three horizontal tiles, are forced, as shown in Fig. 3). The number of tilings of type A is clearly equal to the number of tilings of the remaining area $3 \times (2n-2)$, i.e., the number $a_{n-1}$. Similarly, the number of tilings of type B is equal to the number of tilings of the area $3 \times (2n-3)$ with the cut out bottom right $1 \times 1$ square, i.e., the number $b_{n-1}$. This proves the first equation in (1).

![](https://cdn.mathpix.com/cropped/2024_04_17_7f7149a15f3fd6cbd268g-07.jpg?height=211&width=309&top_left_y=2213&top_left_x=702)

A

![](https://cdn.mathpix.com/cropped/2024_04_17_7f7149a15f3fd6cbd268g-07.jpg?height=223&width=317&top_left_y=2213&top_left_x=1052)

B

Fig. 3

The second equation in (1) is verified similarly with a more concise comment: we divide all tilings of the area $3 \times 2n$ into three disjoint groups - tilings of types C, D, and E shown in Fig. 4. All tilings of type C are clearly $a_{n-1}$, while the numbers of tilings of types D and E are equal to the same number $b_{n}$ (which we have already emphasized). This completes the proof of the second equation in (1).
![](https://cdn.mathpix.com/cropped/2024_04_17_7f7149a15f3fd6cbd268g-08.jpg?height=238&width=1024&top_left_y=566&top_left_x=524)

Fig. 4

We are now ready to calculate the desired number $a_{5}$. From the values $a_{1}=3, b_{1}=1$ and the equations (1), we sequentially obtain

$$
\begin{gathered}
b_{2}=a_{1}+b_{1}=4, a_{2}=a_{1}+2 b_{2}=11, b_{3}=a_{2}+b_{2}=15, a_{3}=a_{2}+2 b_{3}=41 \\
b_{4}=a_{3}+b_{3}=56, a_{4}=a_{3}+2 b_{4}=153, b_{5}=a_{4}+b_{4}=209, a_{5}=a_{4}+2 b_{5}=571
\end{gathered}
$$

Answer. The number of ways to tile the area $3 \times 10$ is 571.

Note 1. As promised in the introduction to the solution, we will now show that the numbers $a_{n}$ of all tilings of the area $3 \times 2n$ with $2 \times 1$ tiles satisfy the recurrence equation

$$
a_{n+2}=4 a_{n+1}-a_{n} \quad \text { for every } n \geqq 1,
$$

so they can be calculated "independently," i.e., without simultaneously calculating the numbers $b_{n}$, which we used in the given solution. The derivation of (2) is performed algebraically, i.e., by eliminating the numbers $b_{n}$ from the relations (1). According to them, we have

$$
\begin{aligned}
a_{n+2} & =a_{n+1}+2 b_{n+2}=a_{n+1}+2\left(a_{n+1}+b_{n+1}\right)= \\
& =3 a_{n+1}+2 b_{n+1}=3 a_{n+1}+\left(a_{n+1}-a_{n}\right)=4 a_{n+1}-a_{n}
\end{aligned}
$$

Furthermore, from the basics of discrete mathematics, it is known that any sequence of numbers $\left(a_{n}\right)_{n=1}^{\infty}$ that satisfies (2) has the representation $a_{n}=C_{1} \lambda_{1}^{n}+C_{2} \lambda_{2}^{n}$, where $\lambda_{1,2}=2 \pm \sqrt{3}$ are the roots of the quadratic equation $\lambda^{2}=4 \lambda-1$ and $C_{1,2}$ are arbitrary constants. These can be determined for our situation from the values $a_{1}=3$ and $a_{2}=11$ and thus arrive at the final formula for the number $a_{n}$ of all tilings of the area $3 \times 2n$ with general $n$ in the form

$$
a_{n}=\frac{3+\sqrt{3}}{6} \cdot(2+\sqrt{3})^{n}+\frac{3-\sqrt{3}}{6} \cdot(2-\sqrt{3})^{n} .
$$