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 ith 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 ith number is the number of the hat drawn by the ith 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!