Question

A person writes n letters and addresses n envelopes; if the letters are placed in the envelopes at random, what is the probability that every letter goes wrong?

Answer 1

Let $u_n$ denote the number of ways in which all the letters go wrong, and let $a,b,c,d......$ represent that arrangement in which all the letters are in their own envelopes.

Now if $a$ in any other arrangement occupies the place of an assigned letter $b,$ this letter must either occupy $a$'s place or some other.
(i) Suppose $b$ occupies $a$'s place. Then the number of ways in which all the remaining $n-2$ letters can be displaced is $u_{n-2}$, and therefore the numbers of ways in which $a$ may be displaced by interchange with some one of the other $n-1$ letters, and the rest be all displaced is $(n-1)u_{n-2}$.
(ii) Suppose $a$ occupies $b$'s place, and $b$ does not occupy $a$'s. Then in arrangements satisfying the required conditions, since $a$ is fixed in $b$'s place, the letter $b,c,d,.....$ must be all displaced, which can be done in $u_{n-1}$ ways; therefore the number of ways in which $a$ occupies the place of another letter but not by interchange with that letter is $(n-1)u_{n-1}$;
$\therefore u_n=(n-1)(u_{n-1}+u_{n-2})$;
From which, we find $u_n-n{u}_{n-1}=(-1{)}^n(u_2-u_1)$.
Also $u_1=0,u_2=1$; thus we finally obtain
$u_n=\lfloor n\{\frac{1}{\lfloor 2}-\frac{1}{\lfloor 3}+\frac{1}{\lfloor 4}-.....+\frac{(-1{)}^n}{\lfloor n}\}$.
Now the total number of ways in which the $n$ things can be put in $n$ places is $\lfloor n$; therefore the required chance is
$\frac{1}{\lfloor 2}-\frac{1}{\lfloor 3}+\frac{1}{\lfloor 4}-.......+\frac{(-1{)}^n}{\lfloor n}$.