1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Recursion Is Stupid

  1. Jul 28, 2004 #1
    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.
     
  2. jcsd
  3. Jul 28, 2004 #2

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  4. Jul 28, 2004 #3
    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.
     
  5. Jul 28, 2004 #4
    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.
     
  6. Jul 28, 2004 #5

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  7. Jul 28, 2004 #6

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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.
     
  8. Jul 28, 2004 #7

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    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?
     
  9. Jul 28, 2004 #8

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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?
     
  10. Jul 28, 2004 #9
    I agree. I tried deducing the recurrence also but it gets complex and complicated very quickly.
     
  11. Jul 28, 2004 #10

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    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]
     
  12. Jul 28, 2004 #11

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Can you think of an easier way to make a tower of size n out of a tower of size n-1?
     
  13. Jul 28, 2004 #12

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  14. Jul 28, 2004 #13

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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...
     
  15. Jul 28, 2004 #14

    NateTG

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  16. Jul 28, 2004 #15
    Yes, but you can also take one 1-in. block from the n-1 in. tower and add a 2-in. block. Etc.
     
  17. Jul 28, 2004 #16

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    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).
     
  18. Jul 28, 2004 #17

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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...
     
  19. Jul 28, 2004 #18

    NateTG

    User Avatar
    Science Advisor
    Homework Helper

    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?
     
  20. Jul 28, 2004 #19
    What are you talking about? Read the first three posts.
     
  21. Jul 28, 2004 #20

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Recursion Is Stupid
  1. Recursion Formula (Replies: 1)

  2. Recursive Ideals (Replies: 2)

  3. Recursion formula (Replies: 2)

  4. Stupid question (Replies: 2)

  5. Stupid Charges (Replies: 6)

Loading...