prove or disprove that $\sum_{k=0}^n (k-1)^2 p_n(k) = n!$

Question

Prove or disprove that $\sum_{k=0}^n (k-1)^2 p_n(k) = n!$ for $n\ge 2,$ where $p_n(k)$ is the number of permutations of $\{1,\cdots, n\}$ with exactly $k$ fixed points.

I know how to show that $\sum_{k=0}^n p_n(k) = n!$ by counting the total number of fixed points among all permutations of length n in two different ways. But the method for this doesn't seem to work when showing that $\sum_{k=0}^n (k-1)^2 p_n(k) = n!.$ I know also that $p_n(k) = {n\choose k}p(n-k)$ and $kp_n(k) = np_{n-1}(k-1)$, where $p(n-k)$ is the number of derangements of length $n-k$. So maybe some sort of induction using these recurrences will help?

Answer 1

Hint: Write this as $$ \sum_k k(k-1)p_k(n) -\sum_k kp_k(n)+\sum_k p_k(n) $$ You already found a neat double-counting argument which shows that the last sum is $n!$. There exist clever double-counting arguments which allow you to simplify the first two sums as well.

For a further hint, see Prove that $\sum_{k = r}^{n} k(k - 1)(k - 2)\cdots(k - r+ 1)D_n(k) = n!$.

Answer 2

I hope this makes sense:

1. $\sum_{k=0}^{n}(k-1)^2p_n(k)=\sum_{k=0}^{n}k(k-2)p_n(k)+\sum_{k=0}^{n}p_n(k)$
   We know $\sum_{k=0}^{n}p_n(k)=n!$ we have to check that $\sum_{k=0}^{n}k(k-2)p_n(k)=0$.\
2. First write it like this:
   $\sum_{k=0}^{n}k(k-2)p_n(k)=\sum_{k=0}^{n}k(k-1)p_n(k)-\sum_{k=0}^{n}kp_n(k)$
3. Compute the last part with the last propriety you gave: $kp_n(k)=np_{n-1}(k-1)$ and use the fact that $p_n(l)=0$ for $l<0$:
   $\sum_{k=0}^{n}kp_n(k)=\sum_{k=0}^{n}np_{n-1}(k-1)=n\sum_{l=0}^{n-1}p_{n-1}(l)=n(n-1)!=n!$
4. Use two times the last propriety you gave: $kp_n(k)=np_{n-1}(k-1)$
   $\sum_{k=0}^{n}(k-1)kp_n(k)=\sum_{k=0}^{n}(k-1)np_{n-1}(k-1)=n\sum_{k=0}^{n}(n-1)p_{n-2}(k-2)=$
   $n(n-1)\sum_{j=0}^{n-2}p_{n-2}(j)=n(n-1)(n-2)!=n!$
5. Combine the results above:
   $\sum_{k=0}^{n}(k-1)^2p_n(k)=n!-n!+n! = n!$

Answer 3

Let $D_n$ denote the number of derangements in $S_n$: it is well known that $$ \sum_{n\geq 0}\frac{D_n}{n!}z^{n} = \frac{e^{-z}}{1-z} \tag{1}$$ (where by convention $D_0=1$) so $D_n = n!\sum_{k=0}^{n}\frac{(-1)^k}{k!}$. It is also clear that $$ p_n(k) = \binom{n}{k}D_{n-k} \tag{2}$$ so $$ \sum_{k=0}^{n}(k-1)^2 p_n(k) = \sum_{k=0}^{n}\binom{n}{k}(k-1)! D_{n-k}=\sum_{k=0}^{n}\binom{n}{k}(n-k-1)^2 D_k = n!\sum_{k=0}^{n}\frac{D_k}{k!}\cdot\frac{(n-k-1)^2}{(n-k)!}\tag{3}$$ where $$ \sum_{m\geq 0}\frac{(m-1)^2}{m!}z^m = e^z(1-z+z^2)\tag{4} $$ so by $(3)$ $$ \sum_{k=0}^{n}(k-1)^2 p_n(k)= n![z^n]\left(\frac{e^{-z}}{1-z}\cdot e^z(1-z+z^2)\right)=n![z^n]\left(1+\frac{z^2}{1-z}\right)\tag{5} $$ and the LHS always equals $n!$, except in the case $n=1$ where it equals $0$.