3
$\begingroup$

Came across the following tile problem :

Given a “2 x n” board and tiles of size “2 x 1″, count the number of ways to tile the given board using the 2 x 1 tiles. A tile can either be placed horizontally i.e., as a 1 x 2 tile or vertically i.e., as 2 x 1 tile.

Recurrence formula is as mentioned below :

count(n) = n if n = 1 or n = 2
count(n) = count(n-1) + count(n-2)

Explanation is as follows :

count(n-1) : If the first tile is placed vertically, then problem reduces to a grid of size "2 x (n-1)"
count(n-2) : If the first tile is placed horizontally, then problem reduces to a grid of size "2 x (n-2)", because we will need to place two tiles horizontally one above the other 

But my doubt is, the above recurrence is fine if we always place the tiles at the left most side of grid. What if I place the first vertical tile at center of grid instead of the left most. Should not be covering all the permutation and combinations possible on basis of where we place the first tile?

$\endgroup$
4
$\begingroup$

Your understanding of reducing the given problem to a subproblem is flawed. Say you have to place the tiles, if you start from the centre and keep on placing the tiles, finally the arrangement you have can also be obtained by placing tiles from the left hand side. You don't want to double count. So the recurrence relation you mentioned is correct.

$\endgroup$
  • $\begingroup$ Definitely, I was missing that small piece in my understanding. $\endgroup$ – Aman Gupta Mar 22 '16 at 14:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.