Combinatorics and not getting your hat

[Alkatran]

We were given an extra credit problem in discrete structures 2 today. The problem is: n people go to a party and leave a hat. When they leave they take a random hat. What is the probability that no one ends up with the same hat?
I can calculate the probability, but I was just wondering if I can simplify this any more. Here is my basic work (obviously a lot of reasoning is left out):

2 people:
2! - 2*1! + 1 = 1

3 people:
3! - 3*2! + 3*1! - 1 = 2

generalized:
<br /> \sum_{x=0}^n _n C_x (n - x)! (-1)^x<br />

simplified:
<br /> \sum_{x=0}^n \frac{n!}{x!}(-1)^x<br />
I know that this needs to be divided by n! to get the probability.

Is there any way to get rid of the summation or simplify in some other way?

edit: just realized I could take the n! out. It's now obvious that the summation stays nicely between 1 and 0... still not sure where to simplify from there.

 

[benorin]

This is a derangement problem and you got it: good job! The number of derangements of n objects, say hats, is variously denoted by D_n or by !n and is given by

D_n=!n=\sum_{k=0}^n \frac{n!}{k!}(-1)^k

EDIT: I fixed the link (it goes to mathworld now).

 

[Alkatran]

Excellent. So I suppose that means there isn't a non-summation (elementary?) formula for the summation of -1 to the x divided by x factorial from 0 to n?

 

[benorin]

!n=\left[ \frac{n!}{e}\right] where [x] is the nearest integer function.

 

[Alkatran]

!n=\left[ \frac{n!}{e}\right] where [x] is the nearest integer function.

I found that one on mathworld too, very nice. Small point though: It doesn't match when n = 0.

I'm going to stick with the summation form: I can show the work to make it there. I have no idea how to reach round(n!/e).

 

[benorin]

Hmm... I'll try.

We know that !n=\sum_{k=0}^n \frac{n!}{k!}(-1)^k=n!\sum_{k=0}^n \frac{(-1)^k}{k!} is, by your combinatorial arguement, an integer, furthermore we have

\frac{n!}{e}=n!e^{-1}=n!\sum_{k=0}^{\infty} \frac{(-1)^k}{k!} = n!\sum_{k=0}^{n} \frac{(-1)^k}{k!} + n!\sum_{k=n+1}^{\infty} \frac{(-1)^k}{k!} = !n+n!\sum_{k=n+1}^{\infty} \frac{(-1)^k}{k!}

so we need to show that the second term in the last equality is less than unity, and we wish to know when it is greater than 0.5 [I think].

Since it is an alternating series, we have an estimation theorem for that... notably, it is also the remainder for a Taylor series (times n!).

 

[benorin]

Also check out (5) on this page

 

[benorin]

Hmm... I'll try.
We know that !n=\sum_{k=0}^n \frac{n!}{k!}(-1)^k=n!\sum_{k=0}^n \frac{(-1)^k}{k!} is, by your combinatorial arguement, an integer, furthermore we have
\frac{n!}{e}=n!e^{-1}=n!\sum_{k=0}^{\infty} \frac{(-1)^k}{k!} = n!\sum_{k=0}^{n} \frac{(-1)^k}{k!} + n!\sum_{k=n+1}^{\infty} \frac{(-1)^k}{k!} = !n+n!\sum_{k=n+1}^{\infty} \frac{(-1)^k}{k!}
so we need to show that the second term in the last equality is less than unity, and we wish to know when it is greater than 0.5 [I think].
Since it is an alternating series, we have an estimation theorem for that... notably, it is also the remainder for a Taylor series (times n!).

so, picking up at the alternating series estimation, we know that the error in estimating \frac{n!}{e} by stopping at the n^th term is less than the absolute value of the next term in the series, hence

\left| \frac{n!}{e} - !n\right| \leq \frac{n!}{(n+1)!} = \frac{1}{n+1}&lt;1,

therefore round it! [but I am tired :zzz: , so have a go at it: I'm likely missing something...]