0
$\begingroup$

In how many ways can a 2 × n rectangular board be tiled using 1 × 2 and 2 × 2 pieces?

What i tried

I used to inclusion exclusion principle where

no of ways the 2 × n rectangular board can be tiled using 1 × 2 AND 2 × 2 pieces

=the no of ways the 2 × n rectangular board can be tiled using 1 × 2 pieces +

no of ways the 2 × n rectangular board can be tiled using 2 × 2 pieces - no of ways the 2 × n rectangular board can be tiled using 1 × 2 OR 2 × 2 pieces

Then solving each of the three parts indivually

no of ways the 2 × n rectangular board can be tiled using 1 × 2 pieces=$(n/2*2)=n$ ways

no of ways the 2 × n rectangular board can be tiled using 2 × 2 pieces =$(n/2)$ ways

no of ways the 2 × n rectangular board can be tiled using 1 × 2 OR 2 × 2 pieces=$(3*n/2)$ ways

Im unsure of my answers. Could anyone please explain. Thanks

$\endgroup$

2 Answers 2

1
$\begingroup$

You have several problems. The question is intended to allow you to mix $1 \times 2$ and $2 \times 2$ pieces. You have assumed that a given tiling only allows one type to be used. Given your assumption, there is only one way to tile using $2 \times 2$ pieces, and that only if $n$ is even. For $1 \times 2$, there are at least as many tilings as if you tile it with $2 \times 2$ blocks, then cut each block in half. As you can cut each block either horizontally or vertically, this accounts for $2^{\frac n2}$ tilings and there are many more.

The intended solution is by a recurrence relation. A tiling of a $2 \times n$ board can either end with a $2 \times 2$ block on the right, a pair of horizontal $1 \times 2$ blocks on the right, or a vertical $1 \times 2$ block on the right. Let $A(n)$ be the number of ways to tile a $2 \times n$ rectangle. Can you write the recurrence based on the first sentence?

$\endgroup$
1
$\begingroup$

What you want to do here is work out a recurrence and then solve it. Let $a_n$ be the number of ways of tiling the $2\times n$ board; we want to express $a_n$ in terms of one or more $a_k$’s with $k<n$.

A tiling of the $2\times n$ board can end in a vertical $1\times 2$ tile, a $2\times 2$ tile, or a pair of horizontal $1\times 2$ tiles. How many tilings of each kind are there?

  • The vertical $1\times 2$ tile can be placed after any tiling of the $2\times(n-1)$ board, so there are $a_{n-1}$ of these tilings of the $2\times n$ board.
  • Either the $2\times 2$ tile or the pair of horizontal $1\times 2$ tiles can be placed after any tiling of the $2\times(n-2)$ board, so there are $2a_{n-2}$ of these tilings.

Thus, $a_n=a_{n-1}+2a_{n-2}$. To finish the problem, you need to work out the initial values for the recurrence (either $a_0$ and $a_1$ or $a_1$ and $a_2$) and then solve the recurrence to get a closed form for $a_n$ in terms of $n$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.