Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

P & c

  1. Oct 6, 2009 #1
    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. jcsd
  3. Oct 6, 2009 #2
  4. Oct 6, 2009 #3


    User Avatar
    Science Advisor

    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?
  5. Oct 6, 2009 #4
    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.
  6. Oct 13, 2009 #5

    Thats correct!!! This can even be done with recursion.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook