Just how many ways are there to get it all wrong!

The Note is correct. If even one letter gets into its correct envelope, that case can not be counted (it is a failure).

The proof of the binomial theorem is recursive in its iteration. It is not necessary to evaluate a binomial coefficient that way though. They can be evaluated as $\binom{n}{k}=\frac{n!}{k! (n-k)!}$ , which is found on some calculators directly and can be done on any calculator with factorial (!).

Using the binomial expansion of $(s-f)^5$ , one can see that it is $-10 f^3 s^2+10 f^2 s^3+5 f^4 s-f^5-5 f s^4+s^5$ . where $s$ represents successes (that is, letters in wrong envelopes) and $f$ represents failures (letters in correct envelopes). This can be generalized using the binomial theorem, noting that the sign changes follow the failures, and there is only one way to have success gives $\sum _{j=0}^5 (-1)^j \binom{5}{j} f^j s^{5-j}$ . Failures ( $f!$ ) are just $(5-j)!$ . Expanding the $\binom{n}{j}$ to its definition and doing the $f$ substitution gives $\sum _{j=0}^5 \frac{5! (-1)^j (5-j)!}{j! (5-j)!}$ which evaluates to $44$ . Generalizing that formula for arbitrary $n$ with a term cancellation and moving a constant $n!$ out of the summation gives $n! \sum _{j=0}^n \frac{(-1)^j}{j!}$ as was stated in the original solution.

As a check, for $n$ from 1 to 9, all the permutations of $n$ objects were generated and the successful permutations were counted directly. The results were the same.

A recursive evaluation of the following table would a very long time. Using the formula method, it takes milliseconds. $\begin{array}{r|r} \text{n} & \text{count} \\ \hline 1 & 0 \\ 2 & 1 \\ 3 & 2 \\ 4 & 9 \\ 5 & 44 \\ 6 & 265 \\ 7 & 1854 \\ 8 & 14833 \\ 9 & 133496 \\ 10 & 1334961 \\ 11 & 14684570 \\ 12 & 176214841 \\ 13 & 2290792932 \\ 14 & 32071101049 \\ 15 & 481066515734 \\ 16 & 7697064251745 \\ 17 & 130850092279664 \\ 18 & 2355301661033953 \\ 19 & 44750731559645106 \\ 20 & 895014631192902121 \\ 21 & 18795307255050944540 \\ 22 & 413496759611120779881 \\ 23 & 9510425471055777937262 \\ 24 & 228250211305338670494289 \\ 25 & 5706255282633466762357224 \\ 26 & 148362637348470135821287825 \\ 27 & 4005791208408693667174771274 \\ 28 & 112162153835443422680893595673 \\ 29 & 3252702461227859257745914274516 \\ 30 & 97581073836835777732377428235481 \\ \end{array}$

Now, read Derangement . Therefore, the limit as $n\to\infty$ of derangments of $n$ objects, also known as, $\text{Subfactorial}(n)$ or $\text{!}n$ , divided by $n!$ can seen easily as $e^{-1}$ . The $n!$ terms cancel and what remains is the series expansion for $e^{-1}$ .