4
$\begingroup$

This question already has an answer here:

enter image description here

$\color{red}{Attempt} $

We start with $k=1$, $P(X=1)$ is the probability that one letter have been put in the correct envelope. Our sample space size is $n$ and since there is only one way that one letter must have been put into the correct envelope and the rest $n-1$ incorrectly and so we see that $P(X=1)= \dfrac{(n-1)!}{n}$, now for $P(X=2)$ it becomes more complicated, so far I know that ${n \choose 2}$ is the size of the sample space and now we want to count the number of ways in which 2 letters must have been put in the correct envelope. First, of all, the $n-2$ letters that have been put incorrectly we have to count them and we have $(n-2)!$ and then the 2 letters that are put correctly this is done in one way thus

$$ P(X=2) = \frac{(n-2)!}{{n \choose 2} }$$

so, in general, we have

$$ P(X=k) = \frac{(n-k)!}{n \choose k } $$

is this correct?

$\endgroup$

marked as duplicate by Parcly Taxel, Don Thousand, Scientifica, Key Flex, user10354138 Oct 16 '18 at 13:40

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ it is a complete different question $\endgroup$ – Mikey Spivak Oct 16 '18 at 0:24
  • $\begingroup$ No, they're exactly the same. $\endgroup$ – Parcly Taxel Oct 16 '18 at 0:25
  • 2
    $\begingroup$ but if I dont even understand the question that you posted, how can I even understand the solutions? $\endgroup$ – Mikey Spivak Oct 16 '18 at 0:30
  • 1
    $\begingroup$ @ParclyTaxel Thanks for posting the reference. These questions both refer to the same concept, but the proposed problem, as well as the desired solution by the poster and its level of explanation, differ. This would be an example of where a duplicate question is beneficial to community users. That being said, Neymar, I suggest a more descriptive title to your question for better searchability. $\endgroup$ – zahbaz Oct 16 '18 at 0:37
  • 1
    $\begingroup$ Unrelated question but isn't $X$ allowed to take the value $0$ as well? Just put the last letter in envelope $1$ and put letter $i$ in envelope $i+1$. This way none of the letters are in the correct envelope $\endgroup$ – WaveX Oct 16 '18 at 0:40
3
$\begingroup$

For $n$ letters there are $n!$ ways to put them in the envelopes, and the number of ways to put them in such that exactly $k$ letters are in the correct envelope can be divided into two factors:

  • the $\binom nk$ ways to choose the correctly placed letters
  • the $S(n-k)$ ways to place the rest of the envelopes so that none of them are in the correct envelope

Thus the probability $P(X=k)$ is $\frac1{k!}\cdot\frac{S(n-k)}{(n-k)!}$ – in particular the expression you derived is wrong.

We now determine $S(n-k)$; write this as $S(m)$. There are $\binom m0(m-0)!$ permutations in all, $\binom m1(m-1)!$ fixing one point, $\binom m2(m-2)!$ fixing two and so on to $m$ fixed points. Then the inclusion/exclusion principle gives the number of permutations with no fixed points as $$\sum_{i=0}^m(-1)^i\frac{m!}{i!}=m!\sum_{i=0}^m\frac{(-1)^i}{i!}$$ Then we have the simplification $$P(X=k)=\frac1{k!}\sum_{i=0}^{n-k}\frac{(-1)^i}{i!}$$ $S(n)$ counts what are called derangements of $n$ objects, and is most often denoted $!n$. With this notation we can also write $$P(X=k)=\frac1{k!}\cdot\frac{!(n-k)}{(n-k)!}$$

$\endgroup$
  • $\begingroup$ what is $S(n-k)$? $\endgroup$ – Mikey Spivak Oct 16 '18 at 0:57
  • $\begingroup$ @Neymar A function which I derive the expression for in the second half of the answer. $m=n-k$. $\endgroup$ – Parcly Taxel Oct 16 '18 at 0:58
  • $\begingroup$ I see but what is a derangement? $\endgroup$ – Mikey Spivak Oct 16 '18 at 0:59
  • $\begingroup$ @Neymar An assigment of letters to envelopes such that no letter ends up in its correct envelope. $\endgroup$ – Parcly Taxel Oct 16 '18 at 0:59
  • $\begingroup$ @Neymar I actually wrote quite an enjoyable answer above! $\endgroup$ – Parcly Taxel Oct 16 '18 at 1:08

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