Derangements

One problem that always interested me is related
to permutations: if you choose an arbitrary permutation,
what is the probability that no number stays in the same place.
In the text books this is known as the hat problem,
but I know it from Sinterklaas parties in which people
must make a surprise for somebody else.
So all names are written on a piece of paper
and everybody must draw a name. What is the
probability that this process succeeds the first time.

The problem is discussed various times in Sheldon Ross's
book, in section 5m. In this approach the
inclusion exclusion principle is used to establish
the sum
1 - 1 + 1/2! - 1/3! + (-1)**N/N! which approached 1/e ~ .36788
See also example 3.5c.

Daniel Marcus also discusses the problem. Permutations
that move all its elements are called derangements,
and he give the first values.

Then in F he gives two recurrence relations:
D_n = (n-1) (D_{n-1} + D_{n-2}) ; n >=3
D_n = n D_{n-1} + (-1)^n ; n>= 2

Today I found a piece of paper which made me remember that
Knuth also discusses this problem [193].
He uses h(n,k), where n is the number of hat owners
and k the number of people that get there hat back,
so D_n = h(n,0).

The following formula is also pretty obvious:
h(n, k) = (n choose k) h(n-k, 0).

He also gives a table which is loaded with structure

n h(n,0) 1 2 3 4 5 6
0 - 1
1 - 0 1
2 - 1 0 1
3 2 3 0 1
4 9 8 6 0 1
5 44 45 20 10 0 1
6 265 264 135 40 15 0 1
(I should program this)

They say that
h(n, 0) - h(n, 1) = (-1)^n and
h(n, n-2) = (n choose 2)
But it also seems that
h(n, 1) = n h(n-1, 0)
and that
h(n, 2) = n/2 h(n-1, 1)
and maybe
h(n, 3) = n/3 h(n-1, 2)
10 = 5/3 * 6
40 = 6/3 * 20
and maybe
h(n, 4) = n/4 h(n-1, 3)
15 = 6/4 * 10

Another observation is that these tables make me thin of
the poisson distribution with lambda=1,
where the values for n=0=1 equals 1/e ~.36788
For n=6 we get
264.87
132.43
44.14
11.03
2.21
so that is close enough


Aah, this is certainly true and it is surprising
that itś not mentioned. Now I only need to figure
out why.

Anyway, what I really liked is that GKP estimate the
error of D_n = h(n, 0) within one integer,
meaning that they can calculate it as
floor( n!/e + .5 )


Buuh, all this stuff is already available on line.
It is actually impressive. See
http://en.wikipedia.org/wiki/Derangement
http://www.research.att.com/~njas/sequences/A000166
http://en.wikipedia.org/wiki/Rencontres_numbers

This thing about the exact approximation is listed also,
anmd my observation about the Poisson distribution
is too. But the relation within the table I have not
found yet.