Prove $\sum_{k=0}^{n}k*p_n(k)=n!$

Question

I simplified the above problem to

Prove$$\sum_{k=1}^n\left(\sum_{i=0}^{n-k}\frac{(-1)^i}{(k-1)!\,i!}\right)=1$$

Here $p_n(k)$ denotes number of permutations of $\{1,2,\dots ,n\}$ such that we have k fixed points.

How to proceed?

Answer 1

There are exactly $n!$ permutations of $\{1, 2, \dots, n\}$, and the equation is just classifying each permutation with respect to number of fixed points.

Answer 2

You have changed the problem in the edit.

You can rewrite $$\sum_{k=0}^n kp_k(n)$$ as $$\sum_{\sigma\in S_n}|\textrm{fix}(\sigma)|$$ where $\textrm{fix}(\sigma)$ is the set of fixed points of $\sigma$. By Burnside's lemma, this equals $n!M$ where $M$ is the number of orbits of $S_n$ on its natural action on $\{1,\ldots,n\}$. But $M=1$.

Answer 3

Answer for the new question. We can adopt the indicator function technique:

Let $S_n$ be the set of permutations on $\{1,\cdots,n\}$. Then for each $\sigma\in S_n$, the number of fixed points of $\sigma$ can be written as $\sum_{i=1}^{n}\mathbf{1}_{\{\sigma(i)=i\}}$. So

$$\sum_{k=0}^{n}k p_n(k) =\sum_{\sigma\in S_n}\sum_{i=1}^{n}\mathbf{1}_{\{\sigma(i)=i\}} =\sum_{i=1}^{n}\sum_{\sigma\in S_n}\mathbf{1}_{\{\sigma(i)=i\}} =\sum_{i=1}^{n}(n-1)!=n!.$$