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
find an expression for
Hello, Tweety!
This problem is bigger than I thought.
I do have some observations.
Maybe others can follow up.
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
Find an expression for
The area can be tiled "horizontally" . . .
or "vertically" . . .Code:*-------*-------* . . | H | H | *-------*-------* | H | H | *-------*-------* . .
or any combination thereof.Code:*---*---*---*---* . . | | | | | | V | V | V | V | | | | | | *---*---*---*---* . .
I reasoned like this:
For each 2-by-2 square, there are two choices:
. . two H's or two V's.
If is even, there are squares
. . which can be tiled in ways.
If is odd, there are squares
. . which can be tiled in ways,
. . plus one V domino.
I thought my work was done . . . wrong!
I did some sketching and found the bigger problem.
For , there are 5 tilings:
Code:*-------*-------* *-------*---*---* *---*-------*---* | | | | | | | | | | | *-------*-------* *-------* | | | *-------* | | | | | | | | | | | | *-------*-------* *-------*---*---* *---*-------*---* *---*---*-------* *---*---*---*---* | | | | | | | | | | | *-------* | | | | | | | | | | | | | | *---*---*-------* *---*---*---*---*
I did some more sketching and found this familiar pattern:
. .
But I have no proof that the Fibonnaci sequence is involved here.