Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Just for fun : What's the next number in this sequence ?

  1. Dec 4, 2003 #1


    User Avatar
    Science Advisor

    0, 1, 2, 9, 44, 265 ...

    Assume that the sequence has no "randomly" assigned values. That is, that (perhaps apart from the first) all the elements can be deduced from the index integer (n=1,2,3, etc) and the preceding values of the sequence.

    I dont claim there is a unique solution or anything, I'm just wondering if anyone can dream up a relation that fits the given data and predicts the next point. :)
    Last edited: Dec 4, 2003
  2. jcsd
  3. Dec 4, 2003 #2
    a0 = 0
    a1 = 1

    from n > 2

    an = n*(an-1 + an-2)

    a2 = 2*(a1 + a0) = 2*(1 + 0) = 2
    a3 = 3*(a2 + a1) = 3*(2 + 1) = 9
    a4 = 4*(a3 + a2) = 4*(9 + 2) = 44
    a5 = 5*(a4 + a3) = 5*(44 + 9) = 265
    a6 = 6*(a5 + a4) = 6*(265 + 44) = 1854
  4. Dec 4, 2003 #3


    User Avatar
    Science Advisor

    I should of course mention that there is a solution and that I didn't just pick those numbers a random or anything annoying like that. :)

    Also it relates to a "real world" problem which I will reveal later.
  5. Dec 4, 2003 #4


    User Avatar
    Science Advisor

    Very well done Guybrush Threepwood, it took you all of about one minute. (quicker than I could type my clarifying follow up post).

    The problem from which the sequence was derived is as follows :

    Consider the problem of matching up n items with their respective owners and doing it randomly. (Just like the recent problem posted here about a waiter handing the five different coats back to the five different patrons in the restaruant).

    I was just trying to work out in how many ways you could get it totally wrong so that nobody at all got their correct item (and hence the probablity of getting every one wrong).

    At first I had some trouble doing it analytically so I just manually enumerated the first few terms and tried to guess the sequence in the hope that it would inspire me to think of an analytic solution.

    What is interesting is that I eventually got an analytically derived solution and it "looked" totally different to my guessed solution, yet did in fact yield an identical sequence when I calculated it.

    Even more interesting is that your solution is different again (to both my solutions) yet also yeilds the same sequence. I'm sure it would be possible to prove that all three sequences are identical, though I haven't got time right now.

    Here are the three sequences.

    1. (Guessed by me) [tex]x_n = n \, x_{n-1} + 2\, {\rm even}(n) - 1[/tex]

    2. (solved by me) [tex]x_n = n! - 1 - \sum_{k=1}^{n-1} {\rm C}_k^n \,x_k [/tex]

    3. Guybrush Threepwood's solution. [tex]x_n = (n-1)\, (x_{n-1} + x_{n-2}) [/tex]

    Note that even(n) is the function that is 1 if n is even and zero if n is odd.

    As you can see my solution is pretty ugly, I like Guybrush's much better. Cool how they all give the same answer though. :)

    PS. Note that I changed the "n" in Guybrush's formula to "n-1" simply to make it consistent with the index set of [1,2,3..] that I had used as opposed to [0,1,2..]
    Last edited: Dec 4, 2003
  6. Dec 4, 2003 #5
    will there be a free beer or something as prize?
  7. Dec 4, 2003 #6


    User Avatar
    Science Advisor

    Actually it's quite an interesting result because the probility of getting every one incorrect ([tex]x_n/n![/tex]) converges pretty quickly to a value of around 37%. So it seems that any time there are about 5 or more items then your chances are quite close to about 37% of total failure. No matter how large you make n, hmmm very interesting. :)
    Last edited: Dec 4, 2003
  8. Dec 4, 2003 #7


    User Avatar
    Science Advisor

    Just a hunch, I think that "37%" is probably actually [tex]e^{-1}[/tex].
  9. Dec 4, 2003 #8
    I'm confused:

    your first solution
    [tex]x_n = n \, x_{n-1} + 2\, {\rm even}(n) - 1[/tex]
    would give for 2
    [tex]x_2 = 2 \, x_{2-1} + 2\, {\rm even}(2) - 1[/tex] = 2*1 + 2*even(2) - 1 = 2 + 2 - 1 = 3

    ah, forget it, you begin your series with index 1....
    too much programming:smile:
    Last edited: Dec 4, 2003
  10. Dec 4, 2003 #9


    User Avatar
    Science Advisor

    Guy, it's just that we were working on different index sets. I edited the above to clarify that but it might not have shown up on your browser yet (try refresh).

    I was working on an index set of [1,2,3...] and you were working on [0,1,2..]. Use my index set and you will see all three results are compatible. :)
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook