How many ways are there to completely cover a 10x2 grid with only 1x1 and 1x3 tiles?
Assumptions : Tiles must completely cover the area without overlapping, or going beyond the 10x2 boundary, and must be oriented in the same direction as the 10x2 grid.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
First off, since the 3x1 tiles only fit in one direction, the two 1x10 rows can be taken independently, and the problem boils down to figuring out how many ways a 10x1 grid can be tiled and then squaring it.
Let N n be the number of ways to tile an nx1 grid.
For a 10x1 grid, the far left tile can either be a 1x1 or a 3x1, and the rest can be filled in either N 7 or N 9 ways. In other words:
N 1 0 = N 9 + N 7
To generalize this, for n > 2 ,
N n = N n − 1 + N n − 3
And clearly,
N 0 = N 1 = N 2 = 1
Solving,
N 1 0 = 2 8
So, the total number of ways to tile a 2x10 grid is:
N t o t a l = N 1 0 2 = 7 8 4