Эта задача перекликается с задачей №15
Вновь рассматриваются перестановки множества {1,2,...n}.
Назовем перестановку правильной, если она не оставляет на месте ни одного элемента множества {1,2,...n}. Сколько существует правильных перестановок для n=20?

Решение

Рассмотрим количество правильных перестановок n-элементного множества R(n) для небольших значений n:
R(1) = 0.
R(2) = 1.
R(3) = 2.
R(4) = 9.
R(5) = 44.
R(6) = 265.
Легко увидеть следующую рекуррентную формулу для r(n):
R(n) = n*R(n-1) + (-1) ⁿ (*)
Однако доказать эту формулу не так просто. Поэтому мы применим несколько иной подход к вычислению R(n).
Введем в рассмотрение еще одну функцию - r(n,i), определяемую как количество перестановок n-элементного множества, переставляющих ровно i элементов.
Ясно, что r(n,i) = C(n,i)*R(i).
Суммируя по всем i, получим: n! = SC(n,i)*R(i) (**)
Отсюда R(n) = n! - SC(n,i)*R(i), где суммировние ведется от 0 до n-1. И мы нашли приемлимую формулу для R(n).
Применив ее к n=20, получим R(20) = 895014631192902121.

Обсуждение

Обращая формулу (**), можно получить следующее выражение для R(n):
R(n) = n!*S(-1)ⁱ/i! (***)
Подставляя выражения для R из (***), в формулу (*) не трудно убедиться в ее справедливости.
Видно, что с ростом n второй сомножитель в (***) стремится к 1/e. Оценивая хвост ряда, не участвующий в (***), можно показать, что R(n) есть n!/e, округленное до ближайшего целого.

Награды

За правильное решение (узнавание) этой задачи Борис Бух получает 8 призовых баллов.