## 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

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.