### 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}= 1 and X_{2}= 2.

**References**

## 0 comments:

## Post a Comment