1
$\begingroup$

If $n$ people put their names in a bag, mix it up, and redraw at random, what is the probability that exactly $i$ people get their names back? I have an expression we learned in class about the number of derangements (permutations in which no elements are mapped to themselves) of $n$ elements, $D_{n}$ as well as the exponential generating function, $D$, and I feel like I could use it to solve this problem, but I'm not sure how. Any advice?

$\endgroup$
  • 1
    $\begingroup$ The number of "favourables" is the number of ways to choose the $i$ people who get their own names, times the number of derangements of $n-i$ objects. $\endgroup$ – André Nicolas Nov 4 '15 at 16:32
  • $\begingroup$ Okay, so you're saying my expression will look something like (n choose i) * $D_{n-i}$ ? That seems too simple (not that I don't believe you), but is there anything else you can say about it? $\endgroup$ – James Thent Nov 4 '15 at 16:39
  • $\begingroup$ Or that expression, over the number of possible outcomes? $\endgroup$ – James Thent Nov 4 '15 at 16:42
  • 1
    $\begingroup$ Yes, we divide the number of favourables by the total number $n!$ of permutations to get the probability. $\endgroup$ – André Nicolas Nov 4 '15 at 16:46
  • $\begingroup$ Thank you! I definitely see intuitively how this is the answer. We have the number of ways we can choose i from n, times the number of ways we can leave n-i unpermuted, over the number of possible permutations. Sound right? $\endgroup$ – James Thent Nov 4 '15 at 16:50
0
$\begingroup$

You can use the expression you learned in class about dearangements $(!n)$.

The number of ways to choose which people gets thier names back is $\binom ni$. And the number of ways to dearrange the others $!(n-i)$ you can calculate. So you get the number of partial dearrangements to $\binom ni\cdot !(n-i)$. therefore the probability is: $$ \frac{\binom ni\cdot !(n-i)}{n!} $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.