а) Заметим прежде всего, что $$\textstyle\sum\limits_{k=0}^np_n(k)=n!,\tag1$$
так как в левой части стоит суммарное число перестановок, имеющих 0, 1, $\ldots$, $n$ неподвижных точек, т. е. просто число всех перестановок. Теперь докажем, что при $1\le k\le n$
$$k\,p_n(k)=n\,p_{n-1}(k-1),\tag2$$
считая, что $p_0(0)=1$. Для этого подсчитаем двумя способами число $N$ пар $(f,i)$, где $f$ — произвольная перестановка $n$ элементов с $k$ неподвижными точками, а $i$ — любая из этих точек ($f(i)=i$). С одной стороны, каждая из этих $p_n(k)$ перестановок входит в $k$ пар, поэтому $N=k\,p_n(k)$. С другой стороны, если $f(i)=i$, то на множестве из $n-1$ элементов, отличных от $i$, перестановка $f$ имеет $k-1$ неподвижных точек, следовательно, каждый из $n$ элементов $i$ входит в $p_{n-1}(k-1)$ пар, т. е. $N=n\,p_{n-1}(k-1)$.
Суммируя равенства (2) по $k=1$, $\ldots$, $n$ и учитывая (1) (с заменой $n$ на $n-1$), получим
$$\textstyle\sum\limits_{k=0}^nk\,p_n(k)=n\sum\limits_{k=1}^np_{n-1}(k-1)=n\cdot(n-1)!=n!.$$
б) Докажем сразу более общее тождество
$$\textstyle s(n,m)=\sum\limits_{k=m}^n\dfrac{k!}{(k-m)!}p_n(k)=n!\tag3$$
при всех $n\ge m$, $m=0$, 1, 2, $\ldots$ (по определению, $0!=1$). При $m=0$ оно совпадает с (1), при $m=1$ — с утверждением а), а при $m=2$ эквивалентно б), поскольку
$$\begin{gather*}
\textstyle\sum\limits_{k=0}^n{}(k-1)^2p_n(k)=
\sum\limits_{k=0}^nk(k-1)\,p_n(k)-\sum\limits_{k=0}^nk\,p_n(k)+\sum\limits_{k=0}^np_n(k)=\\
=s(n,2)-s(n,1)+s(n,0).
\end{gather*}$$
Из тождества (2) следует, что при $1\le m\le k\le n$
$$\begin{gather*}
\dfrac{k!}{(k-m)!}p_n(k)=k(k-1)\ldots(k-m+1)\,p_n(k)=\\
=n(k-1)\ldots(k-m+1)\,p_{n-1}(k-1)=\\
=n(n-1)(k-2)\ldots(k-m+1)p_{n-2}(k-2)=\ldots\\
\ldots=n(n-1)\ldots(n-m+1)p_{n-m}(k-m)=\dfrac{n!}{(n-m)!}p_{n-m}(k-m).
\end{gather*}$$
Суммируем эти равенства по $k=1$, 2, $\ldots$, $n$:
$$s(n,m)=\dfrac{n!}{(n-m)!}s(n-m,0)=n!.$$
Другое доказательство тождества (3) можно получить из почти очевидного соотношения $p_n(k)=C_n^k\,p_{n-k}(0)$, где $C_n^k=\dfrac{n!}{k!\,(n-k)!}$ — число $k$-элементных подмножеств множества из $n$ элементов (число сочетаний).
Наш читатель Л. М. Коганов (Москва) сообщил ещё об одном обобщении этой задачи, принадлежащем американскому математику Дж. Голдману: если $S(q,i)$ — это число разбиений множества $\{1,2,{\ldots},q\}$ на $i$ непустых непересекающихся множеств, то $$\textstyle\sum\limits_{k=0}^nk^q\,p_n(k)=n!\sum\limits_{i=1}^mS(q,i),$$
где $m=\min(n,q)$. Доказательство этого соотношения, предложенное Л. М. Когановым, напоминает вывод формулы (2) и сводится к подсчёту двумя способами количества пар $(f,\phi)$, где $f$ — произвольная перестановка множества из $n$ элементов, а $\phi$ — произвольное отображение множества $\{1,2,{\ldots},q\}$ в множество неподвижных точек перестановки $f$.
