|
||||||||||||||||||
|
Это старая версия документа. СодержаниеММ16Конкурсная задача ММ16 (8 баллов)
Эта задача перекликается с задачей ММ15 Решение
Рассмотрим количество правильных перестановок n-элементного множества R(n) для небольших значений n:
Легко увидеть следующую рекуррентную формулу для r(n):
Однако доказать эту формулу не так просто. Поэтому мы применим несколько иной подход к вычислению R(n). Суммируя по всем i, получим: () Отсюда <m>R(n) = n! - sum{i=0}{n-1}{C(n,i)R(i)}</m>, где суммирование ведется от 0 до n-1. И мы нашли приемлемую формулу для R(n). Применив ее к n=20, получим R(20) = 895014631192902121. Обсуждение Обращая формулу (), можно получить следующее выражение для R(n):
(*)
Подставляя выражения для R из (*), в формулу (*) не трудно убедиться в ее справедливости. перестановки, которые в условии ММ16 называются «правильными», обычно называют «беспорядками». Подробнее про них можно почитать в книжке: Р. Грэхем, Д. Кнут, О. Паташник «Конкретная математика». Награды За правильное решение (узнавание) этой задачи Борис Бух получает 8 призовых баллов.
|
|||||||||||||||||
|
||||||||||||||||||
|