Proof of the Rencontres numbers

[Jncik]

Hi everyone,

I'm reading this article

http://en.wikipedia.org/wiki/Rencontres_numbers

and although I understand the whole concept of these numbers, I can't understand how the author derives this equation

[PLAIN]http://img809.imageshack.us/img809/529/unledid.png

this recursion essentially counts the amount of permutation where no number is at a fixed point in the array of n+2 size

I can count these things for small n's for example let's say n is 3

we have these permuations

1 2 3 -> 3
1 3 2 -> 1
3 1 2 -> 0
2 3 1 -> 0
2 1 3 -> 1

thus the amount we're looking for is 2

but what about any n? this is what the author is calculating, I've spent many hours already and I can't figure out where does this recursion come from and how exactly does he go from the recursion to the final equation which is the following:

[URL]http://upload.wikimedia.org/wikipedia/en/math/d/6/a/d6a38c5b9f46d83ef8310b4288aebe3d.png[/URL]

thanks in advance :)

 

[Nino MMP]

The equation is derived by solving a recursion. A recursion is an equation defining a function in terms of itself. In this case, the recursion is:f(n) = f(n-1) + (n-1)! - (n-1)f(n-2)This recursion can be solved using the substitution method. In this method, you assume a solution to the equation, and then substitute it in the recurrence to see if it satisfies the equation. The assumed solution is of the form:f(n) = A*n! + B*(n-1)! + C*(n-2)! + ...Now substitute this in the recurrence:A*n! + B*(n-1)! + C*(n-2)! + ... = A*(n-1)! + B*(n-2)! + C*(n-3)! + ... + (n-1)! - (n-1)*(A*(n-2)! + B*(n-3)! + C*(n-4)! + ...)Collecting like terms, we get:A*n! - A*(n-2)! = (n-1)!This equation can be easily solved for A, giving us A = 1. Now we can substitute this back into our assumed solution to get:f(n) = n! + B*(n-1)! + C*(n-2)! + ...Now substitute this in the recurrence again:n! + B*(n-1)! + C*(n-2)! + ... = B*(n-2)! + C*(n-3)! + ... + (n-1)! - (n-1)*(B*(n-3)! + C*(n-4)! + ...)Again collecting like terms and solving for B gives us B = 1. Substituting this back in the assumed solution gives us:f(n) = n! + (n-1)! + C*(n-2)! + ...Substituting this in the recurrence one last time gives us:n! + (n-1)! + C*(n-2