Show that $\sum _{k=0}^n \frac{k C_n^k\times!k}{n!}=n-1$

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}$$

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.