# Number of Ways

• Apr 25th 2010, 03:20 AM
cedricc
Number of Ways
Find the number of ways of tiling a "2 x n" rectangle with "1 x 2" and "2 x 2" tiles, given that the edges of the tiles are parallel to those of the rectangle.

I have tried listing ways but that was only working through examples (2 x 1 rectangle, 2 x 2 rectangle, 2 x 3, 2 x 4 and so on, but the number increases very quickly and starts getting quite confusing. It also doesn't solve how many possibilities for n assumably in terms of n. How do i solve this showing working where possible??
• Apr 25th 2010, 04:51 AM
Wilmer
Hard to tell what's allowed:
as example, in a 2 by 2 rectangle, can you have these 5 ways:
1 2by2, or
2 1by2 placed horizontally, or
2 1by2 placed vertically ?
• Apr 25th 2010, 05:16 AM
Soroban
Hello, cedricc!

Quote:

Find the number of ways of tiling a $2 \times n$ rectangle with $1 \times 2$ and $2 \times 2$ tiles,
given that the edges of the tiles are parallel to those of the rectangle.

I have tried listing ways but that was only working through examples
(2 x 1 rectangle, 2 x 2 rectangle, 2 x 3 rectangle, so on),
but the number increases very quickly and starts getting quite confusing.
It also doesn't solve how many possibilities in terms of $n$.

How do i solve this, showing working where possible?

There is nothing wrong with Listing the cases and looking for a pattern.
Quite often, it is the only approach available to us.

I found this list . . .

. . $\begin{array}{cc}
\text{Size} & \text{Tilings} \\ \hline
2\times 1 & 1 \\
2\times 2 & 3 \\
2\times 3 & 5 \\
2\times 4 & 9 \\
2 \times 5 & 15 \\
2\times 6 & 25 \\
2\times 7 & 41 \\
\vdots & \vdots \end{array}$

I see this pattern: Starting with the third term,
. . each number is the sum of the preceding two numbers, plus 1.

That is: . $a_n \;=\;a_{n-1} + a_{n-2} + 1$

That's as far as I dare to go . . .
.
• Apr 25th 2010, 08:45 AM
Wilmer
The On-Line Encyclopedia of Integer Sequences

Enter A001595 in search box
• May 12th 2010, 04:55 AM
cedricc
Quote:

Originally Posted by Soroban
Hello, cedricc!

There is nothing wrong with Listing the cases and looking for a pattern.
Quite often, it is the only approach available to us.

I found this list . . .

. . $\begin{array}{cc}
\text{Size} & \text{Tilings} \\ \hline
2\times 1 & 1 \\
2\times 2 & 3 \\
2\times 3 & 5 \\
2\times 4 & 9 \\
2 \times 5 & 15 \\
2\times 6 & 25 \\
2\times 7 & 41 \\
\vdots & \vdots \end{array}$

I see this pattern: Starting with the third term,
. . each number is the sum of the preceding two numbers, plus 1.

That is: . $a_n \;=\;a_{n-1} + a_{n-2} + 1$

That's as far as I dare to go . . .
.

Considering, what "Wilmer" wrote, doesn't that mean there's more than three possibilities for a 2 by 2??
• May 12th 2010, 06:56 AM
Wilmer
Whoops: I show 3 possibilities; my "5" is a typo; I'll repost:

as example, in a 2 by 2 rectangle, you can have these 3 ways:
1: one 2by2, or
2: two 1by2's placed horizontally, or
3: two 1by2's placed vertically

Soroban's is CORRECT (Rock)
• May 14th 2010, 12:37 AM
cedricc
I see, thank you so much