Expected number of matching "cards". Why is $\sum_{m=0}^n D_{n,m} = \sum_{m=0}^n m \cdot D_{n,m}$? 
Each of n ≥ 2 people puts his or her name on a slip of paper (no two have the same
  name). The slips of paper are shuffled in a hat, and then each person draws one (uni-
  formly at random at each stage, without replacement). Find the average number of
  people who draw their own names.

This problem can be simply solved by using indicator variables. The expected value is equal to 1, independent of $n$. However, for the fun I wanted to do it via the definition of the expected value.
$$E(X) = \sum_{m=0}^n m \cdot P(X=m) = \frac{1}{n!}\sum_{m=0}^n m \cdot D_{n,m}$$
Here, $D_{n,m}$ is the rencontres number or the number of partial derangements of $n$ elements given $m$ fixed points.
Now I thought it was wrong because I knew that the sum must be equal to $n!$ so that I obtain an expected value of 1, but actually $$\sum_{m=0}^n D_{n,m} = n!.$$ However, I found out that
$$n! = \sum_{m=0}^n D_{n,m} = \sum_{m=0}^n m \cdot D_{n,m} = \sum_{m=1}^n m \cdot D_{n,m}$$
Seems like $$D_{n,0} = !n= \sum_{m=1}^n (m-1) D_{n,m}$$
I would be grateful if anybody could shed some light on this!
 A: There's no contradiction. Everything you write is true. Let's define
$$
\alpha = D_{n,0},
$$
$$
\beta = \sum_{m=1}^nD_{n,m},
$$
$$
\gamma = 0 D_{n,0} = 0,
$$
$$
\delta = \sum_{m=1}^nmD_{n,m}.
$$
Then you showed that
$$
\alpha+\beta = \sum_{m = 0}^nD_{n,m} = \sum_{m=0}^nmD_{n,m} = \gamma+\delta.
$$
This looks surprising at first glance - we expect that $\sum_{m = 0}^nD_{n,m} < \sum_{m=0}^nmD_{n,m}$ because of the factor $m$ on the r.h.s. And for "large" $n$, it is indeed true that $\beta < \delta,$ because then for some $m > 1,$ $D_{n,m}$ will be positive. But on the other hand, we have $\gamma \equiv 0$ and $\alpha$ is the number of derangements of $n$, so we have $\alpha\gg \gamma$ for "large" $n.$ We have, for example,
$$
\lim_{n\rightarrow\infty}\frac{!n}{n!} = \frac{1}{e}.
$$
As usual, you can find this, and more information on derangement numbers, here.
A: Here's one way of understanding your relation
$$
D_{n,0}=!n=\sum_{m=1}^n(m-1)D_{n,m}.
$$
The set of permutations of $1,2,\ldots,n$ contains $n!$ elements.  Partition this set into the $(n-1)!$ equivalence classes of size $n$ induced by the equivalence relation $\sigma\sim R\sigma,$ where $R$ rotates the elements of $\sigma=\langle\sigma_1\sigma_2\ldots\sigma_n\rangle$ to the right: $R\langle\sigma_1\sigma_2\ldots\sigma_n\rangle=\langle\sigma_n\sigma_1\sigma_2\ldots\sigma_{n-1}\rangle.$  So $\langle1234\rangle,$ $\langle4123\rangle,$ $\langle3412\rangle,$ $\langle2341\rangle$ are all equivalent, as are $\langle1432\rangle,$ $\langle2143\rangle,$ $\langle3214\rangle,$ $\langle4321\rangle.$
Now each of $1,2,\ldots,n$ is fixed by exactly one permutation in each equivalence class.  For example, the permutation $\langle1234\rangle$ fixes all four of $1,2,3,4,$ while the three equivalent derangements, $\langle4123\rangle,$ $\langle3412\rangle,$ $\langle2341\rangle,$ all fix no elements.  Likewise, the permutation $\langle1432\rangle$ fixes $1$ and $3,$ the equivalent permutation $\langle3214\rangle$ fixes $2$ and $4,$ and the two equivalent derangements $\langle2143\rangle$ and $\langle4321\rangle$ fix no elements.
Since there are $n$ fixed points among the $n$ elements of an equivalence class, a randomly selected element of an equivalence class is expected to have one fixed point.  The same property then clearly holds on the set of all permutations.  Define $f(\sigma)$ to be the number of points fixed by $\sigma,$ and define $g(\sigma)=f(\sigma)-1.$  So the expected value of $g$ if $\sigma$ is selected uniformly at random from an equivalence class is $0,$ and the same holds if $\sigma$ is selected uniformly at random from the set of all permutations.
But $g(\sigma)=-1$ if $\sigma$ is a derangement.  In general it equals $m-1$ if $\sigma$ has $m$ fixed points.  So if we sum $g$ over the elements of an equivalence class, we get zero:
$$
\sum_{\tau\in\{\sigma,R\sigma,\ldots,R^{n-1}\sigma\}}g(\tau)=0.
$$
For example, on the equivalence class $\langle1234\rangle,$ $\langle4123\rangle,$ $\langle3412\rangle,$ $\langle2341\rangle,$ $g$ takes values $3,$ $-1,$ $-1,$ $-1,$ and on the equivalence class $\langle1432\rangle,$ $\langle2143\rangle,$ $\langle3214\rangle,$ $\langle4321\rangle,$ $g$ takes values $1,$ $-1,$ $1,$ $-1.$  In general, the number of $-1$s always equals the sum of the nonnegative values, from which your relation follows.
Added: I should say something about the thought process behind the answer above.  I had hoped to find some sort of natural bijection between the set of derangements and the set of permutations with $m$ fixed points, $m\ge2,$ each transformed, somehow, in $m-1$ different ways.  My first idea along these lines was to notice that $R^j\langle123\ldots n\rangle$ is a derangement for $1\le j\le n-1.$  This suggests that one should convert a permutation with $m$ fixed points into a derangement by cyclically permuting the $m$ fixed elements.  Since there are $m-1$ ways to do that, each permutation with $m$ fixed points gives rise to $m-1$ derangements.  It initially appeared hopeful that this would explain why your identity is true.
Unfortunately, the idea doesn't work because different permutations can produce the same derangement, and some derangements cannot be produced in this way.  For example, $\langle1432\rangle$ has two fixed points, $1$ and $3.$  Permuting these gives $\langle3412\rangle,$ which is a derangement.  Unfortunately, applying the same construction to $\langle3214\rangle$ gives the same derangement.
It then occurred to me that, instead of cyclically permuting the fixed elements, one ought to cyclically permute all the elements.  After playing with this a bit, I found the argument given above, which does not actually produce a natural bijection.  Nevertheless, I do think the argument provides more insight than do the double-sum manipulations in my other answer.  It may still be possible to find something nicer.
A: It occurs to me that I may have misunderstood the intent of your question, so I give this alternative answer.
Are you asking how to show that, for $n\ge0,$ $\sum_{m=0}^nD_{n,m}=n!,$ and that for $n\ge1,$ $\sum_{m=0}^nmD_{n,m}=n!$?  If so, then you can, of course, write
$$
D_{n,m}=\binom{n}{m}D_{n-m,0}=\binom{n}{m}\sum_{j=0}^{n-m}(-1)^j\frac{(n-m)!}{j!}=\frac{n!}{m!}\sum_{j=0}^{n-m}(-1)^j\frac{1}{j!}.
$$
Then you can prove both statements.  The main trick is a change of summation variable.  The double sum
$$
\sum_{m=0}^n\sum_{j=0}^{n-m}f(m,j)
$$
can be rewritten
$$
\sum_{s=0}^n\sum_{m=0}^sf(m,s-m).
$$
We have
$$
\begin{aligned}
\sum_{m=0}^nD_{n,m}&=\sum_{m=0}^n\frac{n!}{m!}\sum_{j=0}^{n-m}(-1)^j\frac{1}{j!}\\
&=\sum_{s=0}^n\sum_{m=0}^s\frac{n!}{m!}(-1)^{s-m}\frac{1}{(s-m)!}\\
&=\sum_{s=0}^n\frac{n!}{s!}\sum_{m=0}^s(-1)^{s-m}\frac{s!}{m!(s-m)!}.
\end{aligned}
$$
The inner sum equals $0$ unless $s=0,$ in which case it equals $1.$  This yields the result.
Similarly, for $n\ge1,$
$$
\begin{aligned}
\sum_{m=0}^nmD_{n,m}&=\sum_{m=0}^nm\frac{n!}{m!}\sum_{j=0}^{n-m}(-1)^j\frac{1}{j!}\\
&=\sum_{s=0}^n\sum_{m=0}^sm\frac{n!}{m!}(-1)^{s-m}\frac{1}{(s-m)!}\\
&=\sum_{s=1}^n\sum_{m=1}^s\frac{n!}{(m-1)!}(-1)^{s-m}\frac{1}{(s-m)!}\\
&=\sum_{s=1}^n\sum_{m=0}^{s-1}\frac{n!}{m!}(-1)^{s-m-1}\frac{1}{(s-m-1)!}\\
&=\sum_{s=1}^n\frac{n!}{(s-1)!}\sum_{m=0}^{s-1}(-1)^{s-m-1}\frac{(s-1)!}{m!(s-m-1)!}\\
\end{aligned}
$$
The inner sum equals $0$ unless $s=1,$ which yields the result.
Added generalization: The two derivations above can be generalized as follows.  Let $r\ge0.$  Then
$$
\sum_{m=0}^nm(m-1)\ldots(m-r)D_{n,m}=\begin{cases}n! & n\ge r,\\ 0 & n<r.\end{cases}
$$
The proof is essentially the same as the second proof above.
An application of this is the computation of the variance in the number of fixed points, which, for $n\ge2,$ equals $1.$  We have, for $n\ge2,$
$$
\begin{aligned}
\text{variance}&=\frac{1}{n!}\sum_{m=0}^n(m-1)^2D_{n,m}\\
&=\frac{1}{n!}\sum_{m=0}^n[m(m-1)-m+1]D_{n,m}\\
&=1-1+1\\
&=1.
\end{aligned}
$$
There are nicer ways to get this result, however.
