(d) Tiling boards (i) Find a recurrence relation and initial conditions for the

Question

(d) Tiling boards (i) Find a recurrence relation and initial conditions for the number of ways to completely cover a 2 x n checkerboard with 1 x 2 dominoes. For example, if 3, one solution is 2 x 3 checkerboard: covered with 3 dominoes: shorthand for same solution Hint: Consider separately the coverings where the position in the top right corner of the checkerboard is covered by a domino positioned horizontally and where it is covered by a domino positioned vertically.] (ii) Check your answer for n 4 by iteratively using your recurrence relation, and by counting the number of these sequences by hand. (iii) How many ways are there to completely cover a 2 × 6 checkerboard with 1 x 2 dominoes?

Explanation / Answer

Solution:

For the above occurence let pn be the number of ways to cover a 2 X n checkerboard. Then P1=1, P2 = 2

Pn = P(n-1) + P(n-2) for n > 2,

so for n = 3

P3 = P2 + P1

     = 2 + 1

     = 3

P3 = 3

so for n = 4 i.e 2 X 4 checkerboard

P4 = P3 +P2

       = 3 + 2

     = 5

P4 = 5

and lastly for n=6 i.e 2 X 6 checkerboard

P6 = P5 + P4

     = 8 + 5

     = 13

P6 = 13

I've also attached the solution for n = 4 to understand the domino covering the checkerboard.

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

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