• Support PF! Buy your school textbooks, materials and every day products via PF Here!

Recursion Is Stupid

  • Thread starter sjaguar13
  • Start date
49
0
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

Science Advisor
Homework Helper
2,559
3
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.
 
49
0
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.
 
1,356
0
AKG said:
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

Science Advisor
Homework Helper
2,559
3
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:

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

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

Hurkyl

Staff Emeritus
Science Advisor
Gold Member
14,845
17
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

Science Advisor
Homework Helper
2,559
3
Hurkyl said:
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

Staff Emeritus
Science Advisor
Gold Member
14,845
17
Something can be far easier, yet still not be easy. :smile: 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?
 
1,356
0
I agree. I tried deducing the recurrence also but it gets complex and complicated very quickly.
 

AKG

Science Advisor
Homework Helper
2,559
3
Hurkyl said:
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.

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

Hurkyl

Staff Emeritus
Science Advisor
Gold Member
14,845
17
Can you think of an easier way to make a tower of size n out of a tower of size n-1?
 

AKG

Science Advisor
Homework Helper
2,559
3
Hurkyl said:
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

Staff Emeritus
Science Advisor
Gold Member
14,845
17
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

Science Advisor
Homework Helper
2,449
5
AKG said:
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:
[tex]t(n)=4f+2t+1o[/tex]
where [tex]f,t[/tex] and [tex]o[/tex] are the four, two and one inch blocks respectively.

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

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.
 
1,356
0
Yes, but you can also take one 1-in. block from the n-1 in. tower and add a 2-in. block. Etc.
 

AKG

Science Advisor
Homework Helper
2,559
3
Hurkyl said:
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

Staff Emeritus
Science Advisor
Gold Member
14,845
17
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

Science Advisor
Homework Helper
2,449
5
e(ho0n3 said:
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?
 
1,356
0
NateTG said:
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

Science Advisor
Homework Helper
2,559
3
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

Staff Emeritus
Science Advisor
Gold Member
14,845
17
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

Science Advisor
Homework Helper
2,449
5
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.
 
1,356
0
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

Science Advisor
Homework Helper
2,559
3
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

Science Advisor
Homework Helper
2,559
3
e(ho0n3 said:
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.
 

Related Threads for: Recursion Is Stupid

  • Posted
Replies
2
Views
1K
Replies
8
Views
3K
  • Posted
Replies
1
Views
1K
  • Posted
Replies
2
Views
1K
  • Posted
Replies
6
Views
2K
  • Posted
Replies
2
Views
1K
  • Posted
Replies
3
Views
1K
  • Posted
Replies
8
Views
1K

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving
Top