ProblemIn how many ways can one tile a 2 X N strip of square cells with 1 X 2 dominos?
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.