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

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?

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