This is the solution to Lab 10. II.3. A few of you asked for it, so here it is!

For the first part, we first calculate the probability of at least one person picking his/her hat back up. We’ll let be the event that the *i*th person picking up his/her hat. We can bound the probability by just taking the sum of the probability that each person takes his/her own hat, . However, this is overestimating by the sum of the probabilities that two people select their own hats, so we need to subtract out the term . But now, we’re underestimating by the sum of the probabilities that three people got their hats. This flips back and forth, adding, and subtracting terms. There’s actually a rule for this: *inclusion-exclusion, *but as usual, it’s better to just know the concept. So the probability of any of them selecting a hat is

If we think of this problem as a list of *N* numbers, where the *i*th number is the number of the hat drawn by the *i*th person, then there are N! possible outcomes. Furthermore, the event that each of *n* people selectes his/her own hat can occur in any of possible ways. For the remaining N-n men, the first can select any of N-n hats, the second can then select any of N-n-1 hats, and so on. Hence we see that .

Also, as there are terms in , we can see that

and, so we can combine everything, to get that

.

For the second part, we apply what we learned in the first. The probability that *k* people can select their own hats is equal to the number of ways in which every other *N – k* person does not pick his/her own hat. We know the probability that none of the *N – k* people picking their own hats is just .

Hence, the number of ways that the people each picking their own hats happens to be the k people we’re looking for is

Furthermore, there are ways to pick k people from N people, so there are

ways that k people pick their own hats.

So the probability we want is just

which simplifies to

Let me know if you got something similar!

I spent a LOT of time on this, and got the idea, but after 2 and a half hours, the math got muddled up so I messed up the plus signs and minus signs

Still, I did understand this, and then of course, I remembered my friend had asked me this question before, so I googled ” Derangement “, and I found it!

So after going through multiple proofs on the internet, I saw how the first part can be generalized to 1/e, which is just kinda nifty.

“e” pops up yet again!