# Thread: Paving a Rectangle

1. ## Paving a Rectangle

I have this problem I need to write a paper on and I'm stuck. You have fifty 2x1 rectangles, which we call dominoes. With these dominoes you want to pave a 2x50 rectangle. How many different ways are there to cover the rectangle? I've tried starting with smaller rectangles to see if I see a pattern but so far no luck. I'm thinking it has something to do with combinations and/or permutations. So far I've found a 2x1 rectangle has 1 way, a 2x2 has 2 ways, a 2x3 has 3 ways, a 2x4 has 5 ways, a 2x5 has 8 ways, a 2x6 has 13 ways and a 2x7 has 21 ways. I'm new to this forum but I've heard wonderful things about it and any help I could get would be greatly appreciated.
Thanks!!!!

2. Originally Posted by peaz9482
I have this problem I need to write a paper on and I'm stuck. You have fifty 2x1 rectangles, which we call dominoes. With these dominoes you want to pave a 2x50 rectangle. How many different ways are there to cover the rectangle? I've tried starting with smaller rectangles to see if I see a pattern but so far no luck. I'm thinking it has something to do with combinations and/or permutations. So far I've found a 2x1 rectangle has 1 way, a 2x2 has 2 ways, a 2x3 has 3 ways, a 2x4 has 5 ways, a 2x5 has 8 ways, a 2x6 has 13 ways and a 2x7 has 21 ways. I'm new to this forum but I've heard wonderful things about it and any help I could get would be greatly appreciated.
Thanks!!!!

Hint - I would try this using recursion

3. Hello, peaz9482!

You have fifty 2×1 rectangles, which we call dominoes.
With these dominoes you want to pave a 2×50 rectangle.
How many different ways are there to cover the rectangle?

I've tried starting with smaller rectangles to see if I see a pattern but so far no luck.

So far I've found:

. . $\begin{array}{cc} \text{Size} & \text{Ways} \\ \hline 2\times1 & 1 \\ 2\times2 & 2 \\ 2\times3 & 3 \\ 2\times4 & 5 \\ 2\times5 & 8 \\ 2\times6 & 13 \\ 2\times7 & 21 \\ \vdots & \vdots \end{array}$
Evidently, you're not familiar with the Fibonacci Sequence,
. . where each term is the sum of the preceding two terms.

The standard form is: . $F_0 = 1,\;F_1 = 1,\;F_n \:=\:F_{n-1} + F_{n-2}$

You want the 50th term: . $F_{50} \;\approx\;1.2586 \times 10^{10}$