Using induction to prove letter arrangement

Question

There are n letters written to different people, and envelopes correspondingly addressed. The letters are mixed before being sealed in envelops, the effect being to make n!allocations of letters to envelops equally likely. We say a letter "matches" if it is placed correctly. Let $A(n,j)$ be the random event that just $j$ letters match. Let $M(n,j)=n!P(A(n,j))$ be the number of the $n!$ permutations of $n$ letters which lead to $j$ matches. Using mathematical induction, show

$$M(n,j)=M(n+1,j+1)\frac{j+1}{n+1}$$

So I tried to prove $M(n+1,j)$ and $M(n+1,j+1)$ but both failed to link $M(n+1,j+1)$ to $M(n+2,j+2)$ or $M(n+2,j+1)$. Could anyone help me with this question?

Answer 1

I think you don't need a powerful tool such as induction to prove this identity. Note that $$ M(n,j)={n \choose j}\cdot M(n-j, 0) \tag{1} $$ say, you first choose $j$ letters that will match the envelop and the remaining will not match. And now it is easy to prove your identity: $$ M(n+1,j+1)={n+1 \choose j+1}\cdot M(n-j,0)=\frac{n+1}{j+1} \cdot {n \choose j} \cdot M(n-j,0)=\frac{n+1}{j+1}\cdot M(n,j) $$

Answer 2

Given $n+1$ letters/envelopes, there are $n+1$ different selections of $n$ letters and their envelopes. Each of these selections can be arranged with exactly $j$ matching letters in $M(n,j)$ ways by inductive assumption. The remaining $(n+1)^{th}$ letter also matches its envelope so this arrangement of the $n+1$ letters matches exactly $j+1$ letters. So, multiplying, we have $(n+1)M(n,j)$ arrangements of $n+1$ letters with exactly $j+1$ matches.

Consider any such arrangement of $n+1$ letters where the numbers of the $j+1$ matching letters are: $m_1,m_2,\ldots,m_{j+1}$. This arrangement has been counted once for each $m_i$ being the $(n+1)^{th}$ number. Therefore, this arrangement has been counted $j+1$ times, meaning we must divide the above count by this number. Hence, the relationship

$$M(n+1,j+1) = \dfrac{n+1}{j+1} M(n,j).$$