## 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."}