Counting Towers: Finding a Recurrence Relation

[sjaguar13]

A set of blocks contains blocks of heights 1, 2, and 4 inches. Imagine constructing towers of piling block of different heights directly on top of one another. Let t(n) be the number of ways to construct a tower of height n inches. Find a recurrence relation for t(1), t(2), t(3)...

Here's what I got:
There are 5 ways to make a tower of 4 inches,
There are 6 ways to make a tower of 5 inches,
There are 10 ways to make a tower of 6 inches.

t(1) = 1, t(2) = 2, and t(3) = 4

t(k) = t(k-1) + t(k-2) - 1, k >= 4

Is that right? I would guess there should be a t(k-3) in there somewhere just because they give you three numbers.

 

[AKG]

First, let's say we're making a tower of 3 inches. Do we count a 2-inch block on top of a 1-inch block different from a 1-inch block on top of a 2-inch block? In other words, does the order of blocks from top to bottom matter? If so, then:

t(1) = 1
t(2) = 2
t(3) = 3
t(4) = 6
t(5) = 10
t(6) = 18
t(7) = 31
t(8) = 50

If order doesn't matter:

t(1) = 1
t(2) = 2
t(3) = 2
t(4) = 4
t(5) = 4
t(6) = 6
t(7) = 6

I can't seem to find a recurrence relation that works.

 

[sjaguar13]

2 on 1 is different then 1 on 2.

I got nothing. I thought it could be t(k) = t(k-1) + t(k-2) + t(k-3) -1, but that quits working near the end. Then I thought it had something to do with powers of 2, but t(5) and t(6) are too close to each other.

 

[e(ho0n3]

If order doesn't matter:

t(1) = 1
t(2) = 2
t(3) = 2
t(4) = 4
t(5) = 4
t(6) = 6
t(7) = 6

I can't seem to find a recurrence relation that works.

Assuming order doesn't matter then for n > 1

t(n) = n if n is even
t(n) = n - 1 if n is odd

It seems the recurrence relation is t(n) = t(n - 2) + 2 for n > 3. I'll play around with this some more and see what happens.

 

[AKG]

When I said I can't seem to find a relation that works, I wrote that after deleting some other stuff, but I guess I forgot I deleted that stuff. Anyway, that stuff said that order probably matters, as the problem wouldn't be much of a problem otherwise. Since order matters, I think the first thing would be to make sure my numbers t(1) through t(8) are right. If those are wrong, then trying to find a relation with wrong numbers will just be a waste of time. Anyways, let me know if you guys agree with that, then we can see where we want to go.

I have a guess:

\forall n > 6,\ \ t(n) = t(n-1) + t(n-2) + t(n-3) - 3^{n-6}

Actually, that doesn't work either, t(9) = 96 as far as I can tell.

 

[Hurkyl]

Well, your problem is that you're trying to guess the recurrence by looking at the numbers. It's far easier to deduce the recurrence based on the problem.

 

[AKG]

Well, your problem is that you're trying to guess the recurrence by looking at the numbers. It's far easier to deduce the recurrence based on the problem.

That's actually not true. I tried to deduce it, it wasn't easy at all. In fact, I got nowhere good, so I didn't post any of those attempts. After that I started looking at the number. I reviewed my numbers, I think I had it wrong, specifically, t(8) should have been 55. Anyways, how should this be deduced then?

 

[Hurkyl]

Something can be far easier, yet still not be easy. Maybe it's clearer to say that it's far harder to try and guess the recurrence based on the numbers.

(Oh, and t(8) = 55)

You've conjectured several times that t(n) = t(n - 1) + (other stuff). So tell me, in what ways can a tower of size n-1 relate to a tower of size n?

 

[e(ho0n3]

I agree. I tried deducing the recurrence also but it gets complex and complicated very quickly.

 

[AKG]

You've conjectured several times that t(n) = t(n - 1) + (other stuff). So tell me, in what ways can a tower of size n-1 relate to a tower of size n?

Lots of ways. If n is odd, then the following algorithm can give t(n).

Find all combinations that give a height of n-1. Let the number of combinations be c. For each combination, let b(i) be the number of blocks in the i'th combination, let O(i) be the number of 1's in the i'th combination, and let p(i) be the number of permutations possible with the i'th combination.

t(n) = \sum _{i = 1} ^{c} p(i)\frac{b(i) + 1}{O(i) + 1}

 

[Hurkyl]

Can you think of an easier way to make a tower of size n out of a tower of size n-1?

 

[AKG]

Can you think of an easier way to make a tower of size n out of a tower of size n-1?

Adding a 1-inch thing. If n is odd, then the only thing you can do is add a 1-inch block to any of the existing combinations. But to find the number requires the calculation I've given. But not only does it not work for n being even, it has nothing to do with recurrence as far as I can tell.

 

[Hurkyl]

I'm not sure why you're making a distinction between even and odd... you can make a size n tower out of a size (n-1) tower by adding a one inch block to the top, no matter what n is...

 

[NateTG]

That's actually not true. I tried to deduce it, it wasn't easy at all. In fact, I got nowhere good, so I didn't post any of those attempts. After that I started looking at the number. I reviewed my numbers, I think I had it wrong, specifically, t(8) should have been 55. Anyways, how should this be deduced then?

Hmm, if you don't care about the ordering, then the tower is a soltion to:
t(n)=4f+2t+1o
where f,t and o are the four, two and one inch blocks respectively.

If you're having trouble, can you figure out?
t'(n)=2t+1o

Similarly, you might have an easier time figuring out the ordered case using only blocks with size 1 and 2 instead of 1, 2 and 4.

 

[e(ho0n3]

Yes, but you can also take one 1-in. block from the n-1 in. tower and add a 2-in. block. Etc.

 

[AKG]

I'm not sure why you're making a distinction between even and odd... you can make a size n tower out of a size (n-1) tower by adding a one inch block to the top, no matter what n is...

I said:

If n is odd, then the only thing you can do is add a 1-inch block

It's not so with even n, so there is reason for distinction. Anyways, where is this going? This is a trivial fact we all certainly realized, we just haven't understood where to go with it. That, if you don't mind, is what we'd like to explore, and I think it'd be better that you guide us onwards there (you can assume we know things like n-1 + 1 = n).

 

[Hurkyl]

Maybe if I phrase it the other way around, it will spark ideas...

Every tower of size n that has a one inch block on top can be made by taking a tower of size (n-1) and putting a one inch block on top of it...

 

[NateTG]

Yes, but you can also take one 1-in. block from the n-1 in. tower and add a 2-in. block. Etc.

I'm not sure if there is a nice recurrance for the unordered case, but as sjaguar indicated, the question is about the ordered case.

P.S. sjaguar, you're really close, so I'll give you a hint: Whats t(0) equal to?

 

[e(ho0n3]

I'm not sure if there is a nice recurrance for the unordered case, but as sjaguar indicated, the question is about the ordered case.

What are you talking about? Read the first three posts.

 

[AKG]

Hurkyl

Sorry, what you said doesn't help

NateTG

I think what you said gave me a hint for some reason, although I can't really say what it was that helped. Acutally, I looked at sjaguar's post and noticed that he mentioned there should be three terms because there are three number, namely 1, 2, and 4. It seems to work given the numbers:

t(n) = t(n-1) + t(n-2) + t(n-4)

This works all the way up to t(10), and it is pretty close to what sjaguar had before (which you, NateTG, said was close). Why this works I'd like to know. Actually, I'm not certain that it works.

 

[Hurkyl]

Ok, you have the right form. Now to figure out why! I was trying not to spoil the deduction... but consider this: there are three ways to have a tower of size n: the top block could be size 1, size 2, or size 4.

 

[NateTG]

I think what you said gave me a hint for some reason, although I can't really say what it was that helped.

There was a tacit assumption that t(0)=0 which is why sjaguar added 1 in his formula to make the result come out right for the first few terms.

 

[e(ho0n3]

Thanks to Hurkyl's last hint, I've figured it out. I think the best hint to give to figure out the problem is:

What are the possible choices for the top (or bottom) block of each n-inch tower config.?

 

[AKG]

NateTG I don't think he assumed t(0) = 0, since he only gave is equation for n>3 or 4 anyways (i.e. t(0) never entered the picture).

Hurkyl, yeah, it all makes sense now, it all seems so simple.

 

[AKG]

Thanks to Hurkyl's last hint, I've figured it out. I think the best hint to give to figure out the problem is:

What are the possible choices for the top (or bottom) block of each n-inch tower config.?

But that gives it away entirely. I suppose he had little choice to either give it away or give us hints that seemed like they wouldn't help at all. Some problems, you can't really give a hint without giving it away.