Suppose you have 5 kinds of wooden blocks: red blocks which are 2 inches high, b

Question

Suppose you have 5 kinds of wooden blocks: red blocks which are 2 inches high, blue

blocks which are 2 inches high, green blocks which are 2 inches high, yellow blocks which

are 3 inches high, and violet blocks which are 3 inches high. Let tn be the number of

ways to build a tower of blocks n inches high by placing blocks one on top of another.

Assume you have an unlimited number of each kind of block.

Find a recurrence relation and initial conditions for tn. Use this recur-

rence relation to compute the number of ways to build a tower 6 inches high.

Explanation / Answer

Note that there are three 2 inch blocks and 2 3 inch blocks. Then, to = 1 t1 = 0 t-1 = 0 Then, for the recursion, for n >= 2 tn = 3 t n-2 + 2 t n-3 (For each of the ways at n-2, we can choose 3 different blocks for the next 2 inches; for each of the ways at n-3, we can choose 2 different blocks for the next 3 inches) (We added t -1 so that we could write this for n = 2; otherwise, we would just start with n = 3). Note that this works for n = 2 (We get 3, as 3 * t o + 2 * t -1 = 3*1+2*0 = 3, which is the right answer) and n = 3 (We get 2, as 3 * t 1 + 2 * t o = 3 * 0 + 2 * 1 = 2, which is the right answer) t 4 = 3 t 2 + 2 t 1 = 3 * 3 + 2 * 0 = 9 t5 = 3 t3 + 2 t2 = 3 * 2 + 2 * 3 = 12 t6 = 3 t4 + 2 t3 = 3 * 9 + 2 * 2 = 27 + 4 = 31 This is the answer that we should have expected. We can either have 3 2 inch blocks or 2 3 inch blocks. As there are 3 different 2 inch blocks and 2 different 3 inch blocks, we get 3 ^ 3 + 2 ^ 2 = 31

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

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