- #1
- 959
- 0
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:
[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.
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.
Last edited: