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?(adsbygoogle = window.adsbygoogle || []).push({});

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:

[tex]2! - 2*1! + 1 = 1[/tex]

3 people:

[tex]3! - 3*2! + 3*1! - 1 = 2[/tex]

generalized:

[tex]

\sum_{x=0}^n _n C_x (n - x)! (-1)^x

[/tex]

simplified:

[tex]

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

[/tex]

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.

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Combinatorics and not getting your hat

**Physics Forums | Science Articles, Homework Help, Discussion**