Re: Challenging Tiling Problem


Found an error. (See below.)

Proginoskes wrote:
> [...]
> Bob wrote:
>
> > (a) How many ways are there can I tile a m x n floor with 1 x 1,
> > 2 x 1 and 2 x 2 tiles?
>
> > (b) Do the above with an additional type of L-shaped tile (2x2 - 1
> > corner) tiles (ie, 4 type of tiles)
>
> The 4 types of tiles include the three in (a) and are the 1x1, 2x1,
> 2x2, and L. If Minus XVII had stopped and thought for 5 minutes, he'd
> have realized this.
>
> Now, back to your question. I think this is going to be a difficult
> question, even if n is 2. There's a couple of related results:
>
> (1) The number of ways to tile a 2 x m board with 2x1 tiles is F(n).
>
> (2) The number of ways to tile a 1 x m board with 1x1 and 1x2 tiles is
> F(n).
>
> (F(n) is the nth Fibonacci number: F(0) = 0, F(1) = 1,
> F(n) = F(n-1) + F(n-2).)
>
> (1) and (2) are proved by setting up a recursive formula. That's
> probably your best bet here; it will get you answers to (a) and (b)
> when n=2.
>
> Let B(a,b) be the number of ways to tile a row of "a" tiles on top of a
> row of "b" tiles. Note that B(a,b) = B(b,a), so we may assume that a >=
> b.
>
> B(a,b) = B(a-1, b) + B(a-2, b), if a >= b + 2. This is because we have
> to put a 1x1 or 2x1 block at the upper right-hand square of a board
> like:
>
> XXXXX
> XX
>
> B(a,b) = B(a-1, b) + B(b, a-2), if a = b + 1. In this situation, we
> have a "board" like:
>
> XXX
> XX
>
> and a 1x1 or 2x1 tile has to cover the square in the upper right.
>
> Now for the last, tricky rule:
>
> B(a,a) = B(a-2,a-2) + B(a-1, a-1) + B(a, a-2) + B(a,a-1).
> 2x2 2x1, vert. 2x1, horiz. 1x1
>
> Here the two rows have the same length. You can have a 2x2 at the far
> right, a 2x1 which is vertical, a 2x1 which is horizontal, or a 1x1 in
> the upper right-hand corner. So the recursive part of B(a,b) (where a
> >= b) is
>
> B(a,b) = B(a-1, b) + B(a-2, b), if a >= b + 2
> = B(a-1, b) + B(b, a-2), if a = b + 1
> = B(a-2,a-2) + B(a-1, a-1) + B(a, a-2) + B(a,a-1), if a = b.
>
> Since the recurrance "goes back" by 1 or 2, we need to find the
> following
> B's:
>
> B(1,1) = 1
> B(2,1) = 2
> B(2,2) = 6 (this one required some work).

Actually, B(1,1) = 2 and B(2,1) = 3. I was doing the problem for the
1x1 and 1x2 boards. D'oh!

> and the rest can be calculated recursively. Of course, you want to find
> B(m,m) to count the number of ways to cover a m x 2 board.

This sequence a_m = B(m,m) does not appear to be in the Online
Encyclopedia of Integer Sequences.

> The situation in (b) when n = 2 is a little more difficult, in that you
> have to add more terms to the recursive definition, to take care of the
> L tiles. (I'd rather wait and see whether I haven't made a mistake with
> the formulas first.)
>
> n >= 3 will definitely be messy, though.

--- Christopher Heckman

.