Простейший пример применения техники производящих функций на
самом деле не использует всего этого ужаса, который мы с вами сейчас изучали,
а, именно, это пример, когда рассматриваются конечные суммы каких-то
довольно хитрых комбинаторных величин.
Ну и в случае, когда суммы конечные, производящая функция – это
просто многочлен, и там о сходимости беспокоиться не приходится.
Ну, давайте рассмотрим первый пример применения производящих функций.
Требуется найти вот такую вот с виду довольно
страшную функцию, я лучше по k буду суммировать.
Сумма по k от 0 до n, видите, конечная сумма,
то есть здесь беспокоиться о сходимости не приходится.
Но, какая?
C из n по k умножить на, скажем, k²,
ну и, давайте на 2/3 в k-той степени.
Ну, сумма выглядит довольно страшно.
Почему?
Потому что здесь присутствует k², который путает, так сказать, все карты.
Но, вот именно k² вроде как путает все карты,
то есть если мы посмотрим вот на такую сумму, по k от 0 до n,
C из n по k на 2/3 в k-той степени, то вот эта сумма, по идее, у людей,
которые разобрались с биномом Ньютона, не должна вызывать никаких трудностей.
Понятно, что даже не такая сумма, а более общая сумма,
когда здесь стоит произвольное число x, вполне себе считается.
Смотрите, давайте обозначим f(x) – это
у нас будет сумма по k от 0 до n, C из n по k,
x в k-той степени, то есть мы заменим нашу конкретную дробь
2/3 на абстрактную переменную x, которая может принимать,
в том числе, значение 2/3, но может принимать и любые другие значения тоже.
Вот.
Ну смотрите, это ни что иное, как производящая функция,
производящая функция последовательности
чисел C из n по 0, C из n по 1, ..., C из n по n.
То есть мы имеем дело с конечной последовательностью,
составляем по ней производящую функцию и, о, радость!
Эта производящая функция считается явно.
Ничего не стоит понять, руководствуясь знанием исключительно бинома Ньютона,
что это есть (1 + x) в n-ной степени, и вся недолга.
Вот такая вот простая штука.
Ну и что, казалось бы?
Да, научились мы считать эту производящую функцию,
но нас-то интересует сумма значений таких величин.
Хе. Ну, замечательно,
давайте её продифференцируем.
Смотрите, что будет, если мы найдем производную f'(x)?
Производную по x, естественно.
У нас получится, здесь надо суммировать от 1,
чтоб всё было аккуратно, k на C из n по k на x в (k − 1).
Понимаете, да, почему от единицы?
Если я здесь подставлю 0, то не будет понятно,
что такое x в (k − 1) формально, всё-таки надо аккуратно здесь тоже делать.
Давайте суммировать от единицы, но, смотрите,
эта штука уже сильно более похожа на ту изначальную, которую нам нужно посчитать.
Ну, не совсем она, но, наверное, вы догадываетесь, что,
если что-нибудь продифференцировать второй раз, то получится ровно то, что нужно.
Вот. Ну,
здесь еще мешается вот эта x в (k – 1).
Всё-таки хочется, наверное, дифференцировать-то x в k-той второй раз,
поэтому давайте сделаем вот так: x * f'(x),
у нас получится сумма по k от 1 до n, k на C из n по k,
и замечательным образом просто на x в k-той степени, как и изначально было.
В принципе, вот здесь уже можно суммировать от 0 равно, как от 1,
разницы никакой не будет, потому что всё равно k = 0, дает нулевое слагаемое.
Ну так, для красоты,
я опять выровнял по левому краю это суммирование и начинаю его от нуля.
Ну а дальше понятно, надо взять производную уже от этого выражения,
x на f'(x) продифференцировать, у нас снова получится
суммирование по k от 1 до n, здесь будет k² на C из n по k,
на x в (k − 1) степени, и это уже практически то,
что нам нужно, особенно, если подставить сюда вместо x – 2/3.
Другой разговор, что, ну опять надо всё-таки умножить на x,
чтобы всё получилось, то есть в итоге надо взять вот такую
штуку: x * (x f'(x))' и,
вычислив это выражение, подставить туда x = 2/3.
Видите, какая замечательная техника, в каком-то смысле думать не надо.
То есть надо углядеть в том выражении, которое мы хотим отыскать,
что-то похожее на то, что умеем считать, сделать такое вот обобщение,
то есть рассмотреть общую производящую функцию, а дальше таким легким
движением рук, без особого напряга дифференцируем,
умножаем, дифференцируем, умножаем, и сумма считается.
Ну, почему считается?
Потому что мы знаем функцию 1 + x в n-ной, вот именно от этой штуки мы будем считать
производную, у нас получится n на (1 + x) в (n − 1) степени,
эту производную мы умножим на x, после чего вычислим производную
от вот такого выражения, это вполне себе чисто техническое действие,
которое не составляет труда, снова умножим на x и подставим x, равное 2/3.
Всё, у нас получилось решение задачи.
Вот, это простейший пример применения техники производящих функций.