设 ${P}_{n}(k)$ 是集 $\{1,\cdots,n\}$ 的保持 $k$ 个不动点的排列数目．求证：$\displaystyle \sum\limits_{k=0}^{n}{k\cdot {{p}_{n}}(k)=n!}$．（联邦德国）
【难度】
【出处】
1987年第28届IMO试题
【标注】
【答案】
略
【解析】
保持 $k$ 个不动点，则其余的 $n-k$ 个点没有一个点是不动的，而 $k$ 个点的选法有 $C_n^k$，所以 $P_{n}(k)=P_{n-k}(0)C_n^k$，
于是
$\begin{aligned}
\sum_{k=1}^nkP_{n}(k)&=\sum_{k=1}^nkP_{n-k}(0)C_n^k\\
&=\sum_{k=1}^nP_{n-k}(0)\cdot k\cdot \frac{n!}{k!(n-k)!}\\
&=\sum_{k=1}^nP_{n-k}(0)\cdot \frac{n\cdot (n-1)!}{(k-1)!((n-1)-(k-1))!}\\
&=n\sum_{k=1}^nP_{n-k}(0)C_{n-1}^{k-1}\\
&=n\sum_{k=1}^nP_{n-1}(k-1)
\end{aligned}$
其中 $\displaystyle \sum\limits_{k=1}^nP_{n-1}(k-1)$ 表示 $n-1$ 个点中没有点不动，或 $1$ 点不动，$\cdots\cdots$，或 $n-1$ 点都不动的排列数，也就是 $n-1$ 个点的全排列数 $(n-1)!$，所以
$\displaystyle \sum\limits_{k=0}^nkP_{n}(k)=n(n-1)!=n!$．
于是
$\begin{aligned}
\sum_{k=1}^nkP_{n}(k)&=\sum_{k=1}^nkP_{n-k}(0)C_n^k\\
&=\sum_{k=1}^nP_{n-k}(0)\cdot k\cdot \frac{n!}{k!(n-k)!}\\
&=\sum_{k=1}^nP_{n-k}(0)\cdot \frac{n\cdot (n-1)!}{(k-1)!((n-1)-(k-1))!}\\
&=n\sum_{k=1}^nP_{n-k}(0)C_{n-1}^{k-1}\\
&=n\sum_{k=1}^nP_{n-1}(k-1)
\end{aligned}$
其中 $\displaystyle \sum\limits_{k=1}^nP_{n-1}(k-1)$ 表示 $n-1$ 个点中没有点不动，或 $1$ 点不动，$\cdots\cdots$，或 $n-1$ 点都不动的排列数，也就是 $n-1$ 个点的全排列数 $(n-1)!$，所以
$\displaystyle \sum\limits_{k=0}^nkP_{n}(k)=n(n-1)!=n!$．
答案
解析
备注
