Recurrence Relations and initial Conditons 1) Suppose that we have a collection

Question

Recurrence Relations and initial Conditons

1) Suppose that we have a collection of building blocks consisting of red, blue, and green blocks of height 1 cm and yellow blocks of height 2cm. Write a recurrence relation and inital conditions for the nubmer of ways to build a stack of height n cm using these blocks.

2) Suppose that poker chips come in four colors - red, white, green, and blue. Write a recrrence relatiosn and inital conditons for the nubmer of ways to stack n of these poker chips so that there are no consecutive blue chips.

Explanation / Answer

1)

Each tower of height n can be produced in 3 ways from one of height n-1 and 1 way from one of height n-2:

So, recurrence relation is :

T(n) = 3T(n-1) + T(n-2)

----------------------------------------------------------------------------------

2)

Each stack of height n with a blue chip on top must have red, white or green beneath it and so can be formed in 3 ways from such a stack with n-2 chips. Or the stack of height n without a blue chip on top may be formed in 3 ways from any such stack with n-1 chips:

So, recurrence relation is :

S(n) = 3S(n-2) + 3S(n-1)

Related Questions

Navigate

• Browse (All)
• Browse R
• Subjects

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