# Thread: word problem sequence / puzzle help

1. ## word problem sequence / puzzle help

A 2 x n rectangular area, where n is a positive integer, is to be titled using non-overlapping 2x1 rectangles.

The number of ways in which a 2 x n rectangular area can be tiled is denoted by $t_{n}$

find an expression for $t_{n}$

2. ## Re: word problem sequence / puzzle help

Originally Posted by Tweety
A 2 x n rectangular area, where n is a positive integer, is to be titled using non-overlapping 2x1 rectangles.
The number of ways in which a 2 x n rectangular area can be tiled is denoted by $t_{n}$
find an expression for $t_{n}$
Are the tiling rectangles each identical or different?
What difference does the orientation of the tile make?

3. ## Re: word problem sequence / puzzle help

I don't really understand the problem my self, but my sheet shows this example,

one tiling for a 2 x 5 area.

and since all rectangles are 2 x 1, i am assuming they are identical ?

4. ## Re: word problem sequence / puzzle help

Originally Posted by Tweety
I don't really understand the problem my self, but my sheet shows this example,
one tiling for a 2 x 5 area.
and since all rectangles are 2 x 1, i am assuming they are identical ?
That diagram does help.
$t_1=1$ one vertical tile. $t_2=2$ two vertical tiles or two horizontal tiles.

What is $t_3=~?$ How are they arranged?

5. ## Re: word problem sequence / puzzle help

Hello, Tweety!

This problem is bigger than I thought.
I do have some observations.

A 2 x n rectangular area, where n is a positive integer,
is to be tiled using non-overlapping 2x1 rectangles ("dominos").

The number of ways in which a 2 x n rectangular area can be tiled is denoted by $T_n.$

Find an expression for $T_n.$

The area can be tiled "horizontally" . . .

Code:
      *-------*-------* . .
|   H   |   H   |
*-------*-------*
|   H   |   H   |
*-------*-------* . .
or "vertically" . . .

Code:
      *---*---*---*---* . .
|   |   |   |   |
| V | V | V | V |
|   |   |   |   |
*---*---*---*---* . .
or any combination thereof.

I reasoned like this:

For each 2-by-2 square, there are two choices:
. . two H's or two V's.

If $n$ is even, there are $\tfrac{n}{2}$ squares
. . which can be tiled in $2^{\frac{n}{2}}$ ways.

If $n$ is odd, there are $\tfrac{n-1}{2}$ squares
. . which can be tiled in $2^{\frac{n-1}{2}}$ ways,
. . plus one V domino.

I thought my work was done . . . wrong!
I did some sketching and found the bigger problem.

For $n=4$, there are 5 tilings:

Code:
      *-------*-------*       *-------*---*---*       *---*-------*---*
|       |       |       |       |   |   |       |   |       |   |
*-------*-------*       *-------*   |   |       |   *-------*   |
|       |       |       |       |   |   |       |   |       |   |
*-------*-------*       *-------*---*---*       *---*-------*---*

*---*---*-------*       *---*---*---*---*
|   |   |       |       |   |   |   |   |
|   |   *-------*       |   |   |   |   |
|   |   |       |       |   |   |   |   |
*---*---*-------*       *---*---*---*---*

I did some more sketching and found this familiar pattern:

. . $\begin{array}{cc} n & T_n \\ \hline 2 & 2 \\ 3 & 3 \\ 4 & 5 \\ 5 & 8 \\ 6 & 13 \\7 & 21 \\ \vdots & \vdots \end{array}$

But I have no proof that the Fibonnaci sequence is involved here.