Show that $\sum _{k=0}^n \frac{k C_n^k\times!k}{n!}=n-1$ I'm trying to solve this problem: $n$ people have $n$ different hats, put all the hats into a box, find the expected value of people that take the wrong hat. We have $n!$ cases, where the probability of $k$ people take the wrong hat (and other $n-k$ people take the correct hat) is $$\frac{!k\times C_n^k}{n!}$$
Where $!k=D_k$ is the derangement number. And the expected value is
$$
\sum _{k=0}^n k\times\frac{C_n^k\times!k}{n!}
$$
Mathematica told me that the value of this expression is $n-1$ for $n=\{1,2,\ldots,100\}$, how to prove it?
 A: The left hand side clearly represent the expected number of people $\mathbb{E}(X)$ who take the wrong hat.
Call the expectation that person $i(=1,2,\ldots,n)$ takes the wrong hat $\mathbb{E}(X_i)$. 
$X_i$ is the discrete random variable which is $1$ if $i$ takes the wrong hat and $0$ if he takes his own hat. The probability that $i$ takes his own hat is $\frac{1}{n}$ and the probability that he takes the wrong hat is $\frac{n-1}{n}$ hence:
$$\mathbb{E}(X_i)=\frac{1}{n}(0)+\frac{n-1}{n}(1)=\frac{n-1}{n}\, .$$
The discrete random variable for the number of people who take the wrong hat is clearly the sum of the random variables for individual cases $X_i$, viz:
$$X=X_1+X_2+\cdots +X_n\, .$$
So the expected number of people who take the wrong hat is
$$\mathbb{E}(X)=\mathbb{E}(X_1+X_2+\cdots +X_n)\, .$$
Then by linearity of expectation we have
$$\begin{align}\mathbb{E}(X)&=\mathbb{E}(X_1+X_2+\cdots +X_n)\\[1ex] &=\mathbb{E}(X_1)+\mathbb{E}(X_2)+\cdots +\mathbb{E}(X_n)\\[1ex] &=n\cdot\frac{n-1}{n}\\[1ex] &=n-1\, .\tag*{$\blacksquare$}\end{align}$$
A: Here is a proof using  exponential generating functions.  The claim is
equivalent to  saying that the  expected number  of fixed points  in a
random permutation is one. This number is represented by the following
combinatorial class:
$$\def\textsc#1{\dosc#1\csod}
\def\dosc#1#2\csod{{\rm #1{\small #2}}}
\textsc{SET}(\mathcal{U}\times \textsc{CYC}_{=1}(\mathcal{Z})
+ \textsc{CYC}_{=2}(\mathcal{Z})
+ \textsc{CYC}_{=3}(\mathcal{Z})
+ \textsc{CYC}_{=4}(\mathcal{Z})
+ \cdots)$$
with EGF
$$G(z, u) =
\exp\left(uz +
\frac{z^2}{2}+\frac{z^3}{3}+\frac{z^4}{4}+\cdots\right)$$
which is
$$\exp\left(uz  - z + \log\frac{1}{1-z} \right)
= \frac{\exp(uz)\exp(-z)}{1-z}.$$
We get for the expectation of the number of fixed points
$$[z^n] \left. \frac{\partial}{\partial u} G(z, u) \right|_{u=1}
\\ = [z^n] \left. z\frac{\exp(uz)\exp(-z)}{1-z} \right|_{u=1}
= [z^n] \frac{z}{1-z} = 1.$$
so there  is indeed one fixed  point on average and  $n-1$ people pick
the wrong hat. 
As for an algebraic proof of
$$\sum_{k=0}^n {n\choose k} k \times !k = (n-1) \times n!$$
we use
$$!k = k! \sum_{q=0}^k \frac{(-1)^q}{q!}.$$
to get
$$\sum_{k=0}^n {n\choose k} k \times
k! \sum_{q=0}^k \frac{(-1)^q}{q!}
= \sum_{k=0}^n {n\choose k} k \times
k! [z^k] \frac{\exp(-z)}{1-z}
\\ = n\sum_{k=1}^n {n-1\choose k-1} \times
k! [z^k] \frac{\exp(-z)}{1-z}
\\ = n \sum_{k=1}^n {n-1\choose k-1} \times
(k-1)! [z^{k-1}]
\left(-\frac{\exp(-z)}{1-z} + \frac{\exp(-z)}{(1-z)^2}\right)
\\ = n \sum_{k=0}^{n-1} {n-1\choose k} \times
k! [z^{k}]
\left(-\frac{\exp(-z)}{1-z} + \frac{\exp(-z)}{(1-z)^2}\right)
\\ = n \sum_{k=0}^{n-1} {n-1\choose k} \\ \times
k! [z^{k}]
\left(-\frac{\exp(-z)}{1-z} + \frac{\exp(-z)}{(1-z)^2}\right)
(n-1-k)! [z^{n-1-k}] \exp(z)
\\ = n \times (n-1)!
[z^{n-1}] \left(\frac{1}{(1-z)^2}-\frac{1}{1-z}\right)
\\ = n \times (n-1)!  (n-1)
= (n-1) \times n!.$$
This is the claim.
