# A Proof Question

Prove :

$$\sum_{k=1}^nkp(n,k)=n!\;,$$

where $p(n,k)$ is the number of permutations of $\{1,2,\ldots, n\}$ which have exactly $k$ fixed points.

I was using $$p(n,k) = \frac{n!}{(n-p)!}$$ and trying to solve this. Substituting $p = 2$ and $n=3$, $\text{LHS}\ne\text{RHS}$, which means that my formula is wrong. Is there any thing that I am missing due to the condition exactly $k$ fixed points?

• This is not an assignment question – algo1 Oct 31 '14 at 13:36
• Generally these types is problems are best solved through induction. – Daniel Goldman Oct 31 '14 at 13:51
• "p(n,k) = n!/(n-k)!" : Thi is false. – Pierre Alvarez Oct 31 '14 at 14:25

One way to tackle it is by induction, using a recurrence for $p$ that can be found here, along with a brief but clear explanation of why it holds:

$$p(n,k)=p(n-1,k-1)+(n-1-k)p(n-1,k)+(k+1)p(n-1,k+1)\;.$$

Assume as an induction hypothesis that

$$\sum_{k=1}^nkp(n,k)=n!\;.$$

Then

\begin{align*} \sum_{k=1}^{n+1}kp(n+1,k)&=\sum_{k=1}^{n+1}k\Big(p(n,k-1)+(n-k)p(n,k)+(k+1)p(n,k+1)\Big)\\\\ &=\sum_{k=0}^nkp(n,k)+\sum_{k=1}^nk(n-k)p(n,k)+\sum_{k=2}^nk(k-1)p(n,k)\\\\ &=\sum_{k=1}^nkp(n,k)+n\sum_{k=1}^nkp(n,k)-\sum_{k=1}^nk^2p(n,k)\\\\&\qquad\qquad\qquad\;\,+\sum_{k=2}^nk^2p(n,k)-\sum_{k=2}^nkp(n,k)\;. \end{align*}

I leave it to you to justify the various changes of index and to complete the calculation by simplifying the last line appropriately.