Ну вот давайте рассмотрим сначала задачу о попойке. То есть нам будут важны слагаемые, в каком они порядке расположены. Давайте введем функцию F(n; n1, ..., nk). Это будет очень простой объект. Это количество разбиений, но повторяю, упорядоченных разбиений, то есть мы находимся в рамках попойки. Количество разбиений числа n натурального на какие-то там слагаемые x1, ..., xt такие, что для любого i xi-тое принадлежит множеству {n1, ..., nk}. Ну в точности та постановка, которая была у нас здесь, только теперь, ну видите, у нас спиртных напитков больше. Их k различных вариантов, и там, соответственно, они весят по-разному. Эти веса обозваны чиселками n1, ..., nk. Спрашивается, вот как посчитать значение этой функции? Ну это как раз совсем просто. Ну что значит «просто»? Можно воспользоваться соображением, которое вы, как многие из вас программисты, хорошо знаете. Оно называется «рекурсия». Можно прибегнуть к знанию каких-то предшествующих значений для того, чтобы вычислить интересующее нас. Ну давайте напишем какое-нибудь рекурентное соотношение для вот этой функции. Какое приходит в голову прежде всего? А? Ну убирать последовательно каждое из них. То есть давайте просто отклассифицируем наше разбиение по тому, сколько было выпито в рамках первого тоста, по объему первой рюмки. Ну он может быть n1, может быть n2, может быть nk – любой. Но поскольку у нас упорядочено все, первая рюмка – это совершенно конкретная вещь. Мы понимаем, что такое первая рюмка. Поэтому пишется просто вот так: F (n − n1; n1, ..., 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). Ну это можно доказать и непосредственно. Это очень простой факт. Но с другой стороны, можно это вывести из рекурентного соотношения, доказанного в прошлый раз с помощью индукции. Если воспользоваться индукцией, то эта теорема тоже очень легко у вас получится.