Пусть
множество всех перестановок длины
,
, тогда
- это количество циклов длины 1 в перестановке
. Требуется доказать, что если
и
, то
.
Иначе последнее равенство можно сформулировать так:
.
Доказательство по индукции у меня, к сожалению, никак не получается провести, так как действует ограничение
и если s не вписывается в данное ограничение, то последнее равенство вообще перестаёт быть верным. Я также пробовал подойти к решению более прямо и подсчитать сколько есть перестановок
для которых
для любого p, вполне конкретную формулу вывести, конечно, получилось, вот только она ничего не даёт.
В конце данного сборника представлено решение, но написано оно в одну строчку и понять его у меня не получилось.
Нужны идеи.