Log In

Tiling a 2xn board

Posted on: January 31st, 2014 by
2

In how many distinct ways can you tile a 2xn board using n pieces of 2x1 dominoes?


2 Responses to Tiling a 2xn board

  1. Sid Hollander had this to say about that:

    Lams' sequence
    F(n+2) = number of binary sequences of length n that have no consecutive 0's.
    Very interesting how frequently this sequence is published.
    See the link below:
    http://oeis.org/search?q=1%2C2%2C3%2C5%2C8&language=english&go=Search

  2. Dinesh had this to say about that:

    Let $f(n) be the number of ways to tile a 2 \cross n board. The very first column can be covered in one of two ways - either by a vertical domino in which case the remaining board can be covered in f(n-1) ways or by a horizontal domino in which case the remaining board can be covered in f(n-2) ways. So, the recursion we get is f(n) = f(n-1)+f(n-2) and the initial conditions are f(2) = 2, f(3) = 3. Thus, f(n) is a Fibonacci number.


{"result":"error", "message":"You can't access this resource as it requires an 'view' access for the website id = 1."}