Question: In how many ways can one tile a 2 X N strip of square cells with 1 X 2 dominos?
Answer: Please notice that we can put tiles either vertically or horizontally. For putting vertical tiles, we need a gap of at least 2 X 2. For putting horizontal tiles, we need a gap of 2 X 1. Number of arrangements will be the same as the arrangements, we can make with gaps of 1 and 2 (order dependent). In this manner, this problem reduces to find the number of ways to partition N using the numbers 1 and 2 with order considered relevant.
For example: 11 = 1 + 2 + 2+ 1 +2 + 2 + 1
If we have to find such arrangements for 12, we can either place a 1 in the end or can add 2 in the arrangements possible with 10.
Similarly, Lets say we have Xn possible arrangements for N. Then for (N+1), we can either place just 1 in the end. Or we can find possible arrangements for (N-1) and put a 2 in the end.
Going by above theory: Xn+1 = Xn + Xn-1
Lets verify above theory for our original problem:
In how many ways, we can fill a 2 X 1, strip:
- 1 -> only one vertical tile.
In how many ways, we can fill a 2 X 2, strip:
- 2 -> Either 2 horizontal or 2 vertical tiles.
In how many ways, we can fill a 2 X 3, strip:
- 3 -> either put a vertical tile in 2 solutions possible for 2 X 2 strip or put 2 horizontal tiles in only solution possible for 2 X 1 strip. (2 + 1 = 3)
Similarly in how many ways, we can fill a 2 X N, strip:
- Either put a vertical tile in solutions possible for 2 X (N-1) strip or put 2 horizontal tiles in solution possible for 2 X (N-2) strip. (Xn-1 + Xn-2).
That’s how, we verified that our final solution:
Xn = Xn-1 + Xn-2
Above recurrence relation is nothing but Fibonacci Series with X1 = 1 and X2 = 2.
I am confident that all the readers can write a optimized code for fibonacci series very easily. Try writing a working code with memoization.
Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.