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