Задача из журнала «Квант» (1987 год, выпуск 12)

Пусть [latex]p_{n}\left(k\right)[/latex]  — число перестановок множества из [latex] n (n \geq 1) [/latex] элементов, имеющих ровно $k$ неподвижных точек. Докажите, что:

1. [latex] \sum\limits_{k=0}^n k \cdot p_{n}\left(k\right) = 0 \cdot p_{n}\left(0\right)+1 \cdot p_{n}\left(1\right)+\ldots+n \cdot p_{n}\left(n\right) = n![/latex]
2. [latex] \sum\limits_{k=0}^n \left(k-1\right)^2 \cdot p_{n}\left(k\right) = n![/latex]

Примечание

Перестановкой конечного множества $S$ называется взаимно однозначное отображение $f$ множества $S$ на себя; число всех перестановок множества из $n$ элементов равно [latex] n! = 1 \cdot 2 \cdot \ldots \cdot n [/latex]

Доказательство

1. Заметим прежде всего, что $$\begin{equation}
   \sum\limits_{k=0}^n p_{n}\left(k\right) = n!,
   \end{equation}
   $$ так как в левой части стоит суммарное число перестановок, имеющих $0,1,\ldots,n$ неподвижных точек, т.е. просто число всех перестановок. Теперь докажем, что при $1 \leqslant k \leqslant n$ $$\begin{equation}
   k \cdot p_{n}\left(k\right) = n \cdot p_{n-1} \cdot \left(k-1\right),
   \end{equation}
   $$ считая, что $p_{0}\left(0\right) = 1 $. Для этого подсчитаем двумя способами число $N$ пар $\left(f,i\right)$, где $f$ — произвольная перестановка $n$ элементов с $k$ неподвижными точками, а $i$ — любая из этих точек $f\left(i\right)=i$. С одной стороны, каждая из этих $p_{n}\left(k\right)$ перестановок входит в $k$ пар, поэтому $N=k \cdot p_{n}\left(k\right)$. Суммируя равенства (2) по $k = 1,\ldots,n$ и учитывая (1) ( с заменой $n$ на $n-1$), получим $$\sum\limits_{k=0}^n k \cdot p_{n}\left(k\right) = n \cdot \sum\limits_{k=1}^n p_{n-1}\left(k-1\right) = n \cdot \left(n-1\right)! = n!$$
2. Докажем сразу более общее тождество $$\begin{equation}
   s\left(n,m\right) = \sum\limits_{k=m}^n \frac {k!}{\left(k-m\right)!} \cdot p_{n}\left(k\right) = n!
   \end{equation}$$ $n \gneq m$, $m = 0,1,2,…$ (по определению, $0!=1$). При $m=0$ оно совпадает с (1), при $m=1$ — с утверждением 1, а при $m=2$ эквивалентно 2, поскольку $$ \begin{multline*} \sum\limits_{k=0}^n \left(k-1\right)^2 \cdot p_{n}\left(k\right) = \sum\limits_{k=0}^n k \cdot \left(k-1\right) \cdot p_{n}\left(k\right) — \sum\limits_{k=0}^n k \cdot p_{n}\left(k\right)+{}\\{}+\sum\limits_{k=0}^n p_{n}\left(k\right) = s\left(n,2\right)-s\left(n,1\right)+s\left(n,0\right). \end{multline*} $$
   Из тождества (2) следует, что при $1\le m\le n\le k$ $$ \begin{multline*} \frac {k!}{\left(k-m\right)!} \cdot p_{n}\left(k\right) = k \cdot \left(k-1\right) \cdot \ldots \cdot \left(k-m+1\right) \cdot p_{n}\left(k\right) = {}\\ {}=n \cdot \left(k-1\right) \cdot \ldots \cdot \left(k-m+1\right) \cdot p_{n-1}\left(k-1\right) = {}\\ {} = n \cdot \left(n-1\right) \cdot \left(k-2\right) \cdot \ldots \cdot \left(k-m+1\right) \cdot p_{n-2}\left(k-2\right)= {}\\ {} = n \cdot \left(n-1\right) \cdot \ldots \cdot (n-m+1) \cdot p_{n-m}\left(k-m\right)= {}\\ {} = \frac {n!}{\left(n-m\right)!} \cdot p_{n-m}\left(k-m\right). \end{multline*} $$ Суммируем эти равенства по $k = 1,\ldots,n$: $$s\left(n,m\right)=\frac {n!}{\left(n-m\right)!} \cdot s\left(n-m,0\right) = n! $$
   Другое доказательство $(3)$ можно получить из почти очевидного соотношения $p_{n}\left(k\right) = C^k_{n} \cdot p_{n-k}\left(0\right)$, где $C^k_{n} = \frac {n!}{k! \left(n-k\right)!}$ — число $k$ -элементных подмножеств множества из $n$ элементов (число сочетаний).