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

[uart]

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 don't 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. :)

 

[Guybrush Threepwood]

a₀ = 0
a₁ = 1

from n > 2

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

so
a₂ = 2*(a₁ + a₀) = 2*(1 + 0) = 2
a₃ = 3*(a₂ + a₁) = 3*(2 + 1) = 9
a₄ = 4*(a₃ + a₂) = 4*(9 + 2) = 44
a₅ = 5*(a₄ + a₃) = 5*(44 + 9) = 265
a₆ = 6*(a₅ + a₄) = 6*(265 + 44) = 1854

 

[uart]

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.

 

[uart]

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 probability 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) $$x_n = n \, x_{n-1} + 2\, {\rm even}(n) - 1$$

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

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

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..]

 

[Guybrush Threepwood]

Originally posted by uart
Very well done Guybrush Threepwood, it took you all of about one minute.

will there be a free beer or something as prize?

 

[uart]

Actually it's quite an interesting result because the probility of getting every one incorrect ($$x_n/n!$$) 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. :)

 

[uart]

Just a hunch, I think that "37%" is probably actually $$e^{-1}$$.

 

[Guybrush Threepwood]

I'm confused:

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

edit
ah, forget it, you begin your series with index 1...
too much programming

 

[uart]

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. :)