If $S=\{1,2,\dots,n\}$ and $P_n(k)$ be the number of permutations of $S$ having $k$ fixed points, then $\sum_{k=0}^nk.P_{n}(k)=n!$ 
Let $S = \{1,2,\dots,n\}$. Then $i \in S$ is said to be a fixed point of a permutation $p$ or $S$ if $p(i) = i$. Let $P_n(k) $ be the number of permutations of $S$ which have $k$ fixed point.
Prove that $\sum_{k=0}^nk\cdot P_{n}(k) = n!$.

 A: Redundant Aunt gave the easiest solution, but since you mention derangements in a comment, here’s one using them:
$$\begin{align*}
\sum_{k=0}^nkP_n(k)&=\sum_{k=0}^nk\binom{n}kD_{n-k}\\
&=n\sum_{k=0}^n\binom{n-1}{k-1}D_{n-k}\\
&=n\sum_{k=0}^{n-1}\binom{n-1}kD_{n-1-k}\\
&=n(n-1)!\\
&=n!
\end{align*}$$
I used the identity $k\binom{n}k=n\binom{n-1}{k-1}$ and the fact that the last summation simply counts all of the permutations of $[n-1]$ according to the number $k$ of elements that they leave fixed.
A: In words:
We overcount the permutations which have a fixed point. If $i\in\{1,...,n\}$, then there are $(n-1)!$ permutations which fix $i$, because we can arrange the other $n-1$ number as we want. If we take the sum over all $i\in\{1,...,n\}$ then we will count a permutation with $k$ fixed points exactly $k$ times. Because there are $P_n(k)$ such permutations and $k$ can take any number in $\{0,...,n\}$ we obtain:
$$
\sum_{k=0}^{n}k\cdot P_n(k)=\sum_{i=1}^{n}(n-1)!=n!
$$
In formulas:
We doublecount the number of elements in $A:=\{(i,\sigma)\in\{1,...,n\}\times S_n\ \mid\ \sigma(i)=i\}$. We have
$$
|A|=\sum_{1≤i≤n}\sum_{\substack{\sigma\in S_n \\ \sigma(i)=i}}1=\sum_{1≤i≤n}(n-1)!=n!
$$
but also (if $\operatorname{fix}(\sigma)$ denotes the number of fixed points of a permutation $\sigma\in S_n$)
$$
|A|=\sum_{\sigma\in S_n}\sum_{\substack{1≤i≤n \\ \sigma(i)=i}}1=\sum_{\sigma\in S_n}\operatorname{fix}(\sigma)=\sum_{k=0}^{n}\sum_{\substack{\sigma\in S_n \\ \operatorname{fix}(\sigma)=k}}\operatorname{fix}(\sigma)=\sum_{k=0}^{n}\sum_{\substack{\sigma\in S_n \\ \operatorname{fix}(\sigma)=k}}k=\sum_{k=0}^{n}\left(k\cdot\sum_{\substack{\sigma\in S_n \\ \operatorname{fix}(\sigma)=k}}1\right)={\sum_{k=0}^{n}k\cdot P_n(k)}
$$
and thus ${\sum_{k=0}^{n}k\cdot P_n(k)}=n!$.
A: The identity has a probabilistic interpretation and probabilistic proof.  Note that if $F(\pi)$ is the number of points left fixed by a permutation $\pi$, and $S_n$ is the set of permutations of $\{1, 2, 3, \dots , n\},$ then$$\sum_{\pi \in S_n} F(\pi) = \sum_{k=0}^n k P_n(k)$$
Write the desired identity in the form
$$\sum_{\pi \in S_n} \frac{1}{n!} F(\pi) =\sum_{k=0}^n \frac{1}{n!} k P_n(k) = 1$$
The probabilistic interpretation is that if we assume all $n!$ permutations are equally likely, then the expected number of fixed points in a random permutation is $1$.  This always seems surprising to me, because the result is independent of $n$.
Here is the proof.  Define
$$X_i = 
\begin{cases}
1   &\text{if i is a fixed point of the permutation} \\
0   &\text{otherwise}
\end{cases}$$ for $i = 1, 2, 3, \dots , n$.
If $i$ is a fixed point, then the remaining $n-1$ elements of $\{1,2,3, \dots ,n\}$ can be arranged in $(n-1)!$ ways, so
$$\Pr(X_i = 1) = \frac{(n-1)!}{n!} = \frac{1}{n}$$
Then
$$E\left( \sum_{i=1}^n X_i \right) = \sum_{i=1}^n E(X_i) = n \cdot \frac{1}{n} = 1$$
i.e., the expected number of fixed points is $1$.
In the above we have made use of the theorem that $E(X+Y) = E(X) + E(Y)$.  This holds even if $X$ and $Y$ are not independent.
