0
$\begingroup$

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?

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.