# P & c

1. Oct 6, 2009

### injun_joe

I've been wondering a lot, but I'm not satisfied with my solution.
Can anyone tell me the TOTAL number of ways to tile a floor of area 9*3 with similar tiles of area 3*1??

2. Oct 6, 2009

Any1??

3. Oct 6, 2009

### mathman

It would help if you could give a little more detail about the question. Are the tiles all different? Are you primarily concerned about tile orientation?

4. Oct 6, 2009

### awkward

Let's define T(n) = the number of ways to tile an n by 3 rectangle with tiles of size 3 by 1.

By inspection, T(1) = T(2) = 1, and T(3) = 2.

Suppose n > 3. Let's say the rectangle is n units long in the X direction and 3 units high in the Y direction. Consider the tile placed at the lower left hand corner of the rectangle. The tile must be either placed vertically or horizontally. If it's placed vertically, with its long axis running parallel to the Y axis, then there are T(n-1) ways to tile the remaining (n-1) by 3 rectangle. If it's placed horizontally, with its long axis running parallel to the X axis, then there must be two more horizontal tiles stacked directly on top of it, and there are then T(n-3) ways to tile the remaining (n-3) by 3 rectangle. So T(n) = T(n-1) + T(n-3).

From these relations, we can compute T(4) = 3, T(5) = 4, ..., with the result T(9) = 19.

5. Oct 13, 2009

### injun_joe

Thats correct!!! This can even be done with recursion.