Arranging letters in envelopes, Permutations and Combinations

Question

If the number of ways to arrange k letters into k envelopes so that none of them are in the right envelope is u[k], prove that u[k+1]=k(u[k]+u[k-1].)

I thought that the answer was u[k] = kC(k-1) * (k-1)C(k-2) ... * 2 as there would progressively be less spots to take up.

Answer 1

Hint.

You are working with derangements and practicizing the notation that you meet in the link you are asked to prove that $$!(k+1)=k[!k+!(k-1)]$$

You can place letter $k+1$ in a wrong envelop and there are $k$ candidates. Distinguish the following cases:

• letter $k+1$ is placed in envelop $i\in\{1,\dots,k\}$ and letter $i$ is placed in envelop $k+1$.

• letter $k+1$ is placed in envelop $i\in\{1,\dots,k\}$ and letter $i$ is not placed in envelop $k+1$.

Answer 2

Call such an arrangement (where no letter ends up in the right envelope) a derangement. Name the letters $L_1, \ldots, L_{k+1}$ and name the envelopes $E_1, \ldots, E_{k+1}$. We thus have the following problem:

\begin{array}{|c|c|c|c|c|c|} \hline \text{Restricted Letter} & L_1 & L_2 & L_3 & \cdots & L_{k+1} \\ \hline \text{Derangement} & ? & ? & ? & \cdots & ? \\ \hline \end{array}

Let's focus on $E_1$. Since $E_1$ can't contain $L_1$, it must contain some other letter.

Assume for now that $E_1$ contains $L_2$. Then where would $L_1$ end up? There are exactly two possibilities:

• Case 1: Suppose that $L_1$ is in $E_2$ (that is, the two simply swapped):

\begin{array}{|c|c|c|c|c|c|} \hline \text{Restricted Letter} & L_1 & L_2 & L_3 & \cdots & L_{k+1} \\ \hline \text{Derangement} & L_2 & L_1 & ? & \cdots & ? \\ \hline \end{array}

This leaves $(k + 1) - 2 = k - 1$ remaining letters (namely, $L_3, \ldots, L_{k+1}$) and envelopes (namely, $E_3, \ldots, E_{k+1}$) that need to be deranged. This can happen in $u[k - 1]$ ways.

• Case 2: Suppose that $L_1$ is not in $E_2$:

\begin{array}{|c|c|c|c|c|c|} \hline \text{Restricted Letter} & L_1 & L_1 & L_3 & \cdots & L_{k+1} \\ \hline \text{Derangement} & L_2 & ? & ? & \cdots & ? \\ \hline \end{array}

This leaves $(k + 1) - 1 = k$ remaining letters (namely, $L_1, L_3, \ldots, L_{k+1}$) and envelopes (namely, $E_1, E_3, \ldots, E_{k+1}$, where we've renamed $E_2$ to be $E_1$) that need to be deranged. This can happen in $u[k]$ ways.

Observe that the above argument still works if we replace $L_2$ with any of the other letters ($L_3, \ldots, L_{k+1}$), for a total of $k$ possiblities. Thus, we conclude that: $$ u[k + 1] = k(u[k - 1] + u[k]) $$