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

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?

## marked as duplicate by Anvit, Community♦Jun 11 '18 at 5:59

• That sounds like the reverse of simplification. – Lord Shark the Unknown Jun 11 '18 at 4:21
• Should the inner sum go from $0$ to $k-1$? – Lord Shark the Unknown Jun 11 '18 at 4:40

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.

• Sorry I missed a $k$ in the equation in the title. Does your argument still hold with the $k$? – Anvit Jun 11 '18 at 5:46

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!.$$

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

• Is there any more elementary way? I Dont think I'll be allowed to use burnside's lemma without proving it – Anvit Jun 11 '18 at 5:47