Кострикин Сборник задач по алгебре 5.3

[Paul Ivanov]

Пусть $S_n$ множество всех перестановок длины $n$, $\sigma\in S_n$, тогда $|\left\lbrace i|\sigma(i)=i\right\rbrace|=N(\sigma)$ - это количество циклов длины 1 в перестановке $\sigma$. Требуется доказать, что если $\sum\limits_{\sigma\in S_n}^{}N(\sigma)^s=\gamma(s)n!$ и $1\leqslant s\leqslant n$, то $\gamma(s+1)=\sum\limits_{k=0}^{s-1}\binom{s}{k}\gamma(s-k)+1$.
Иначе последнее равенство можно сформулировать так: $\sum\limits_{\sigma\in S_n}^{}N(\sigma)^{s+1}=\sum\limits_{\sigma\in S_n}^{}(N(\sigma)+1)^s$.
Доказательство по индукции у меня, к сожалению, никак не получается провести, так как действует ограничение $1\leqslant s\leqslant n$ и если s не вписывается в данное ограничение, то последнее равенство вообще перестаёт быть верным. Я также пробовал подойти к решению более прямо и подсчитать сколько есть перестановок $\sigma\in S_n$ для которых $N(\sigma)=p$ для любого p, вполне конкретную формулу вывести, конечно, получилось, вот только она ничего не даёт.
В конце данного сборника представлено решение, но написано оно в одну строчку и понять его у меня не получилось.
Нужны идеи.

[SiberianSemion]

Полезно рассмотреть сумму $\sum\limits_{\sigma\in S_n, \sigma(i)=i}{N(\sigma)^s}.$ Её удобно свести к случаю с $n-1$ элементами; дело в том, что элемент $i$ остается на месте, поэтому дело фактически сводится к перестановкам $n-1$ элементов. Делая это для каждого элемента $i,$ можно получить требуемое соотношение между $\gamma(s).$

После этого останется доказать, что $\sum\limits_{\sigma\in S_n}{N(\sigma) = n!},$ или, что равносильно, $\gamma(1)=1.$ В этом плане есть продвижения?

[vpb]

Общая идея: когда в задаче есть натуральный параметр, сначала надо ее пытаться решать при малых значениях параметра. Конкретно для данной задачи: выяснить, чему равно $\gamma(1)$, $\gamma(2)$, $\gamma(3)$ (и написать подробное доказательство для этих случаев). А там, возможно, общую идею увидите (или во всяком случае помогающим будет легче объяснить Вам, в чем эта общая идея состоит). В частности, присоединяюсь к вопросу

SiberianSemion в сообщении #1390663 писал(а):

доказать, что $\sum\limits_{\sigma\in S_n}{N(\sigma) = n!},$ или, что равносильно, $\gamma(1)=1.$ В этом плане есть продвижения?

[Paul Ivanov]

SiberianSemion,vpb, спасибо, идею поймал. Этот план действительно рабочий.