Prove using combinatorics $\sum\limits_{k=0}^n (k-1)^2 D_n(k)=n!$.

$D_n(k)$ is the number of permutations of $n$ numbers that exactly $k$ numbers are in their place.

With some calculations I saw that it is not true for $n=1$ so the condition $n \ge 2$ should also be added.I got an algebric proof here.But I need one using combinatorics.For expressing $(k-1)^2$ maybe it is useful to extend it because we cant use $(k-1)^2$.So we got:

$\sum\limits_{k=0}^n k^2*D_n(k)-2*\sum\limits_{k=0}^n k*D_n(k)+2*\sum\limits_{k=0}^n D_n(k)$

It is easy to prove that the second one is $-2n!$ and the third is ,$n!$ so we have to prove:

$\sum\limits_{k=0}^n k^2*D_n(k)=2*n!$

But how should I do that?

  • $\begingroup$ $k-1$ is just $k-1$, the biggest problem is to notice that the LHS is telescopic. $\endgroup$ Jun 6 '17 at 15:49
  • $\begingroup$ @JackD'Aurizio But we need a combinatoral proof so we can't simplify and then show that. $\endgroup$ Jun 6 '17 at 16:15
  • $\begingroup$ Prove in a combinatorial way that the LHS is telescopic. $\endgroup$ Jun 6 '17 at 16:17
  • $\begingroup$ @JackD'Aurizio How should I do that? $\endgroup$ Jun 6 '17 at 16:30
  • $\begingroup$ By mimicking the usual approach for finding $D_n(0)=n!\sum_{k=0}^{n}\frac{(-1)^k}{k!}$. $\endgroup$ Jun 6 '17 at 16:33

$\sum\limits_{k=0}^n k^2*D_n(k)=\sum\limits_{k=0}^nk*D_n(k)+\sum\limits_{k=0}^nk(k-1)*D_n(k)=n!+\sum\limits_{k=0}^nk(k-1)*D_n(k)$

For finding the amount of $\sum\limits_{k=0}^nk(k-1)*D_n(k)$ notice that it is equal to $\sum\limits_{k=2}^nk(k-1)*D_n(k)$.And that is putting $k$ people in their seats and choose one boss and one manger.For that we can choose the boss and manager first($n(n-1)$) ways and put the other randomly so we have:

$$\sum\limits_{k=0}^n k^2*D_n(k)=2*n!$$


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.