Fit 1*2 dominos in 2*N strip

Problem

In how many ways can one tile a 2 X N strip of square cells with 1 X 2 dominos?

Solution

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 X_n 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: X_n+1 = X_n + X_n-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. (X_n-1 + X_n-2).

That’s how, we verified that our final solution:

X_n = X_n-1 + X_n-2

Above recurrence relation is nothing but Fibonacci Series with X₁ = 1 and X₂ = 2.

References

• http://tech-queries.blogspot.in/search/label/Algorithm