A set of blocks contains heights 1, 2, and 4 centimeters. Imagine constructing t

Question

A set of blocks contains heights 1, 2, and 4 centimeters. Imagine constructing towers by piling blocks of different heights directly on top of one another. (A tower of height 6 cm could be obtained using six 1-cm blocks, three 2-cm blocks one 2-cm block with one 4-cm block on top, one 4-cm block with one 2-cm block on top, and so forth.) Let t be the number of ways to construct a tower of height n cm using blocks from the set. (Assume an unlimited supply of blocks from each size.) Find a recurrence relation for t1, t2, t3,...

Explanation / Answer

Let tn = number of ways of constructing height n.

The last block of a tower of height n can be a 1, 2, or 4.
So it was added to a tower of height n-1, n-2, or n-4 respectively.

Let's try: tn = t[n-1] + t[n-2] + t[n-4] . . .

1 = 1 from 1
2 = 2 from (2) or (1,1)
3 = 3 from (1,1,1) or (2,1) or (1,2)
4 = 6 from (1,1,1,1) (1,1,2) (1,2,1) (2,1,1) (2,2) (4)

5 = 10 from
1 x (1,1,1,1,1)
4 x (1,1,1,2)
3 x (1,2,2)
2 x (1,4)

6 = 18 from
2 x (4,2) ....
3 x (4,1,1) ...
1 x (2,2,2) .....
6 x (2,2,1,1) ....
5 x (2,1,1,1,1) ...
1 x (1,1,1,1,1,1) ..

Prediction for 7 is t6 + t5 + t3 = 18 + 10 + 3 = 31

6 x (4,2,1)
4 x (4,1,1,1)
4 x (2,2,2,1)
10 x (2,2,1,1,1)
6 x (2,1,1,1,1,1)
1 x (1,1,1,1,1,1,1)
Total =31

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

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