You have a supply of three kinds of tiles: two kinds of 1 times 2 tiles and one

Question

You have a supply of three kinds of tiles: two kinds of 1 times 2 tiles and one kind of 1 times 1 tile, as shown in the figure. Let x_a be the number of different ways to cover a 1 times n rectangle with these tiles. For example, the following figure shows that there are five ways to fill a 1 times 3 block with the three kinds of tiles, so x_3 = 5. Find x_1, x_2 and x_4 by list all possibilities of covering the blocks, like the above graph. Let x_k = [x_k+1 x_k] be a vector. Set up a recurrence relation x_k+1 = Ax_k for some 2 times 2 matrix. You need to dearly explain how you obtain the connecting matrix A Use x_1 = [x_2 x_1] as the initial condition, and compute a general formula of x_k and x_k. Use this formula to find how many ways then? are to cover a block of size 1 times 6.

Explanation / Answer

Let's denote tile 1 as T1, tile 2 as T2 and tile 3 as T3

(1)

x1 = 1 (because only 1st tile can be used)

x2 = 3 [ 2 T1 ], [1 T2 ], [1 T3 ]

x4 = 11 { [ 4 T1 ], 3*[2 T1 &1 T2 ], 3*[2 T1 & 1 T3 ], [2 T2], [2 T3], 2*[1 T2 + 1 T3 ] }

Rest of the question is not clearly visible.

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.