Различия

Здесь показаны различия между двумя версиями данной страницы.

--- marathon:problem_16 [2015/10/05 19:13]
letsko создано
+++ marathon:problem_16 [2015/10/05 19:27] (текущий)
letsko
@@ Строка 18: / Строка 18: @@
 Легко увидеть следующую рекуррентную формулу для r(n):\\
-R(n) = nR(n-1) + (-1) n (*)
+R(n) = nR(n-1) + (-1)<sup>n</sup> (1)
 Однако доказать эту формулу не так просто. Поэтому мы применим несколько иной подход к вычислению R(n).\\
@@ Строка 24: / Строка 24: @@
 Ясно, что r(n,i) = C(n,i)R(i).
-Суммируя по всем i, получим: <m>n! = sum{i=0}{n-1}{C(n,i)R(i)}</m> (**)
+Суммируя по всем i, получим: <m>n! = sum{i=0}{n-1}{C(n,i)R(i)}</m> (2)
-Отсюда <m>R(n) = n! - sum{i=0}{n-1}{C(n,i)R(i)}</m>, где суммирование ведется от 0 до n-1. И мы нашли приемлемую формулу для R(n).
+Отсюда <m>R(n) = n! - sum{i=0}{n-1}{C(n,i)R(i)}</m>
+И мы нашли приемлемую формулу для R(n).
 Применив ее к n=20, получим R(20) = 895014631192902121.
@@ Строка 32: / Строка 34: @@
 **Обсуждение**
-Обращая формулу (**), можно получить следующее выражение для R(n):
+Обращая формулу (2), можно получить следующее выражение для R(n):
-<m>R(n) = n! sum{i=0}{n-1}(-1){i}/{i!}</m> (***)
+<m>R(n) = n! sum{i=0}{n-1}(-1){i}/{i!}</m> (3)
-Подставляя выражения для R из (***), в формулу (*) не трудно убедиться в ее справедливости.\\
+Подставляя выражения для R из (3), в формулу (1) не трудно убедиться в ее справедливости.\\
-Видно, что с ростом n второй сомножитель в (***) стремится к 1/e. Оценивая хвост ряда, не участвующий в (***), можно показать, что R(n) есть n!/e, округленное до ближайшего целого.
+Видно, что с ростом n второй сомножитель в (3) стремится к 1/e. Оценивая хвост ряда, не участвующий в (3), можно показать, что R(n) есть n!/e, округленное до ближайшего целого.
 перестановки, которые в условии ММ16 называются "правильными", обычно называют "беспорядками". Подробнее про них можно почитать в книжке: Р. Грэхем, Д. Кнут, О. Паташник "Конкретная математика".