nk) +...
+ F (n − nk; n1, ..., nk).
Так, поднимите руки, кто понимает, как доказывать это утверждение.
Я его, в принципе, уже доказал.
Не все, да?
Не все.
Ну давайте еще раз я это проговорю, раз вопрос есть.
Сейчас я быстренько докажу, и, наверное, на этом мы закончим.
Действительно, уже время подходит к концу, и ничего путного я рассказать все
равно не успею, а в следующий раз будет много времени.
Так, доказательство: ну пусть у нас есть какое-то
разбиение числа n на слагаемые x1 +...
+ xt.
Ясно, что либо x1 = n1,
либо x1 = n2,
..., либо x1 = nk.
Мы просто можем вот так каждое разбиение определить: то ли мы сначала выпили водки,
то ли мы сначала выпили вина, то ли пива, ну, в общем, как получится.
Вот.
Ну смотрите: что значит, что x1 = n1,
например, вот в этом случае что у нас получится?
У нас получится, что мы число n − n1 (видите, мы просто перекидываем
x1 влево) представили в виде суммы каких-то слагаемых x2 +...
+ xt.
Ну поскольку изначально мы же не оговаривали,
чему равняется t, оно могло быть каким угодно, то и здесь,
по сути, стоит совершенно произвольное множество слагаемых.
Таким образом, мы здесь получаем произвольное разбиение,
произвольное разбиение числа
n − n1 на слагаемые
величины ну n1, ..., nk, какой-то, не знаю, какой.
У нас же может быть несколько рюмок водки или несколько рюмок пива, это пожалуйста.
Здесь то же самое, но только мы n − nk представляем,
опять же, в виде такой вот суммы слагаемых.
Ну и все, общее количество слагаемых,
общее количество разбиений – это F (n, n1,...
nk) – это количество вот таких разбиений, скобка закрывается.
Количество разбиений вот такого типа – это, конечно,
F (n − n1) – нам надо вот это число представить в виде суммы, ну а сумма,
опять же, чисел любых из вот этого множества n1, ..., nk,
ну и в последнем случае у нас будет F (n − nk; n1, ..., nk).
Поскольку мы четко понимаем, что такое первое слагаемое,
мы все расклассифицировали и получили вот эту сумму.
Так, друзья, я все доказал?
Нет, не все.
Я еще не сказал начальное условие.
Ну тривиальным образом F (0;
и любых n1, ..., nk) = 1.
Ну можно, конечно, продолжать карнавальничать и сказать,
что 0 грамм можно набрать одним способом – ничего не выпивая, да?
Вот, а кроме того, можно написать,
что если здесь формально подставить отрицательное число,
то его вообще нельзя представить в виде суммы положительных слагаемых.
Нет, ну вы, конечно, можете мне давать какие-нибудь карнавальные интерпретации
того, как можно набрать отрицательное число грамм спиртового эквивалента, но,
конечно, это все-таки делается нулем способов, с разумной точки зрения,
чтоб вы там не подумали.
Вот этих начальных условий и такой рекурсии, в принципе, хватает,
чтобы быстро вычислить любое значение функции F.
Давайте я вот сделаю такое обозначение: φ(n) – это у
меня будет F(n; 1, 2, ..., n).
Ну, вообще, я очень рад желанию вникать в науку как можно глубже,
то есть, пожалуйста, да, будем стараться вас всячески радовать
интересными результатами в комбинаторике и теории чисел.
Итак, φ(n) – это вот такая вот величина.
То есть я надеюсь, что вы понимаете,
что φ(n) – это просто количество всевозможных разбиений числа n.
Если вы видите после точки с запятой вот эти все чиселки,
вы понимаете, что в качестве слагаемых вы можете использовать все что угодно.
Тривиальная теорема,
которую я просто озвучу и оставлю вам в качестве упражнения.
Она сразу, если хотите, вытекает из формулы, доказанной в прошлый раз.
Она утверждает, что φ(n) есть не что иное, как просто 2 в степени (n − 1).
Ну это можно доказать и непосредственно.
Это очень простой факт.
Но с другой стороны, можно это вывести из рекурентного соотношения,
доказанного в прошлый раз с помощью индукции.
Если воспользоваться индукцией, то эта теорема тоже очень легко у вас получится.