Метод производящих функций

12

число способов взвешивания груза в $k$ грамм рассматриваемых гирями!

Итак, для решения исходной задачи остается вычислить $A_k$. И здесь — очередной неожиданный ход Эйлера. Он пишет оченьные тожества

$$\begin{align*} (1-z) (1+z) &= 1-z^2, \\ (1-z^2) (1+z^2) &= 1-z^4, \\ (1-z^4) (1+z^4) &= 1-z^8, \end{align*}$$

а после перемножения и сокращения на общие множители получает

$$1-z (1+z) (1+z^2) (1+z^4) (1+z^8) \cdot \dots = 1,$$

то есть $(1-z) \alpha(z) = 1$, откуда

$$\alpha(z) = \frac{1}{1-z} = 1+z+z^2+z^3+z^4+\dots$$

(здеся написана хорошо вам известная формула суммы геометрической прогрессии*). Сравнение (3) с (2) показывает, что $A_k = 1$ для всех $k$, то есть всякийгруз в целое число граммов можно взвести цирами в 1, 2, 4, …, $2^m$, … граммов, при этом единственный способом.

Задача о разбиении числа

Так Эйлер называл следующую задачу: найти число положительных целых решений уравнения

$$x_1 + \dots + x_m = k,$$

(4)

еде $m$ и $k$ — фиксированные натуральные числа. Здесь к целю приводит другое неожиданное выражение, именно

$$\beta(z) = (1+z+z^2+z^3+z^4+\dots)^m.$$

После раскрытия скобок, $\beta(z)$ записывается в виде

$$\beta(z) = 1+B_1z+B_2z^2+B_3z^3+\dots$$

(6)

Чему равно $B_k$? Попробуйте ответить на этот вопрос сами, имея в виду, что $B_k$ — коэффициент при $z^k$. Да, разумеется: коэффициент $B_k$ равен числу способов выбора по одному целому показателю из каждой из скобок в правой части (5), то есть $B_k$ равно числу положительных целых решений уравнения (4)!

Задача Эйлера свелась к вычислению $B_k$.

Для этого, вспомним формулу геометрической прогрессии, можно написать

$$\beta(z) = (1-z)^{-m} = 1+B_1z+B_2z^2+B_3z^3+\dots$$

(7)

Дифференцируя это равенство

$$m(1-z)^{-m-1} = B_1+2B_2z+3B_3z^2+\dots$$

и подставляя $z=0$, получаем $B_1=m$.

*) Если $|z|<1$. Но к этому мы еще вернемся.

Дифференцируя еще раз и вновь подставляя $z=0$, получаем $B_2=m(m+1)/2$. Продолжая точно так же (то есть продолжениеравов (7) $k$ раз и подставив $z=0$), мы получаем, следуя Эйлеру, число решений уравнения (4) в виде

$$B_k = \frac{m(m+1) \cdot \dots \cdot (m+k-1)}{n!}$$

Задача о размене

Сколькоми способами можно разменять рубль монетами достинством 1, 2, 3, 5, 10 копеек? Эту задачу можно сформировать иначе: сколько неотрицательных целых решений имеет уравнение

$$x_1+2x_2+3x_3+5x_4+10x_5=100?$$

В более общем виде «задачу о размене» ставят так: сколько неотрицательных целых решений имеет уравнение

$$a_1x_1+a_2x_2+\dots+a_mx_m=n,$$

(8)

если $a_i$ — целые положительные числа, а $n$ — фиксированное натуральное число?

Рассмотрим выражение

$$\gamma(z) = (1+z^a_1+z^a_2+z^a_3+\dots) \times (1+z^a_2+z^a_2+z^a_3+\dots) \times (1+z^a_m+z^a_m+z^a_m+\dots) = 1+C_1z+C_2z^2+C_3z^3+\dots$$

Если вы поняли предыдущие рассуждания, вы сразу скажете, что число $C_n$ равно числу решений уравнения (8). Но как найти $C_n$? Пользовать формулу суммы бесконечного убывающего геометрического прогрессии (например, $1+z^a_1+z^a_2+\dots=1/(1-z^a_1))$, можно $\gamma(z)$ представить в виде

$$\gamma(z) = \frac{1}{(1-z^a_1)(1-z^a_2)\dots(1-z^a_m)},$$

но от сюда сразу не ясно, как получить $C_n$ в общем случае. Однако уже формулы (9) достаточно, чтобы найти $C_n$ при малых $n$.

Задача о четырех квадратах

Всякое ли целое число можно представить в виде суммы четырех квадратов целых чисел, а если можно, то сколькими способами? Другими словами, сколько целых решений имеет уравнение

$$x_1^2+x_2^2+x_3^2+x_4^2=m,$$

(10)

еде $m$ — данное натуральное число?

Эта задача потребнее предыдущих, хотя она сводится к как и они, к вычислению коэффициентов неокоторого «бесконечного многочлена». Именно, положив

13

$$\delta(z) = \frac{1 + 2z + 2z^4 + 2z^9 + 2z^{16} + \dots}{1 + D_1z + D_2z^2 + D_3z^3 + \dots},$$

легко понять, что число искомых решений уравнения (10) равно $D_m$. Дифференцируя $m$ раз и подставляя $z=0$, можно найти $D_m$ в виде

$$D_m = \frac{1}{m!} \frac{d^m}{dz^m} \left( \delta(z) \right) |_{z=0}$$

где $\frac{d^m}{dz^m}$ обозначает взятие производной $m$-го порядка, а символ $|_{z=0}$ означает, что всему вместе $z$ нужно подставить 0. Для малых $m$ число $D_m$ можно сосчитать по этой формуле, но в общем виде это не непросто. Исходная задача по теории чисел сведена к некоторой задаче из анализа, но последнюю нужно еще решить!

Из результатов немецкого математика К. Г. Якоби (1804—1851) следует замечательная формула для $\delta(z)$

$$\delta(z) = 1 + 8 \sum_{m \neq 4k} \frac{mz^m}{1 - z^m},$$

которую также получил индийский математик С. Рамануджан (1887—1920). Из нее можно вывести, что уравнение (10) всегда разрешимо, и найти число решений этого уравнения.

Обсуждение метода

Попробуем теперь понять, в чем состоит общий метод, так удивительно сравотвший в разобранных задачах. В каждой из них рассматривалось некое «бесконечное выражение», содержащое букву $z$ (бесконечное произведение двучелов — (1), конечная степень бесконечной суммы — (5) и (11), произведение бесконечных сумм — (9)). Далее это выражение записалось в виде «бесконечного многочлена от $z$», то есть в виде

$$\alpha(z) = A_0 + A_1z + A_2z^2 + A_3z^3 + \dots + A_nz^n + \dots,$$

и выясалось, что коэффициенты $A_k$ дают ключ к решению задачи. Коэффициент $A_k$ удалалось затем вычислить, производя разные операции над бесконечными выражениями: выполнялисьарифметические действия над ними, они дифференцировались, преобразовавались по формуле геометрической прогрессии…

Естественно спросить: что представляют собой рассматриваемые нами бесконечные выражения, и законны ли те действия, которые над ними производились? Автор метода, Леонард Эйлер, видимо, не очень задумывался над этим вопросами — он операровал с бесконечными выражениями как с конечными, для него было важно лишь получение результата. Между тем беспечное обращение с бесконечностью tant в себе опасность ошибок.

Претенрный пример

Рассмотрим два «бесконечных многочлена»

$$\alpha(z) = 1 - z + z^2 - z^3 + z^4 - \dots,$$

$$\beta(z) = -1 + z - z^2 + z^3 - z^4 + \dots$$

и посчитаем бесконечную сумму

$$S(z) = \alpha(z) + \beta(z) + \alpha(z) + \alpha(z) + \dots$$

Если группировать слагаемые в $S(z)$ попарно, начиная с первой пары, получим

$$S(z) = [\alpha(z) + \beta(z)] + [\alpha(z) + \beta(z)] + \dots = \alpha(z) + 0 + 0 + \dots = \alpha(z)!$$

Не если группировать иначе, можно получить

$$S(z) = \alpha(z) + [\beta(z) + \alpha(z)] + [\beta(z) + \alpha(z)] + \dots = \alpha(z) + 0 + 0 + \dots = \alpha(z)!$$

А если менять порядок слагаемых, то можно прийти к еще более странному результату, например, $S(z) = 17z^{17}$ (подумайте, как это можно сделать).

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

Формальные степени ряды

Формальные степени рядом называется выражение

$$\alpha(z) = a_0 + a_1z + a_2z^2 + \dots + a_nz^n + \dots,$$

где $a_i$ — действительные числа (козффициенты ряда (12)), а $z$ — простым символом (форманая переменная ряда). Математики говорят также, что $\alpha(z)$ является производящей функцией для последовательности коэффициентов $a_0, a_1, \dots, a_n, \dots$. Не следует думать, однако, что в рассматриваемом нами общем случае $\alpha(z)$ является функцией от переменной $z$ в общим смысле. Когда мы говорим, что $\alpha(z)$ — производающая функция от последовательности $a_0, a_1, \dots, a_n, \dots$, это значит лишь то, что $\alpha(z)$ является сокращенной записью формального выражения в правильной части (12).

Для читателей, знакомых с понятием (обучного) степени ряда, подчеркием, что формальный ряд (12) может рассматриваться (при некоторых $z$ или даже при всех $z$), но при этом равенство (12) остается законным: ведь $\alpha(z)$ обозначает не сумму ряда для данного значения $z$, а сам формальный ряд.

Выдающийся немецкий математик К. Вейерштрасс (1815—1897), развивший и поставивший на сторую логическую основу степени рядов, рассматривал лишь сходящей степени ряды, и критиковал Эйлер заCommitные трики с «бесконечными многочленами». Современная алгебраическая теория формальных степени рядов, которое мы здесь касаемся, выполняется, однako по сути ближе к «наивному» подходу Эйлера, чем к строю аналитической теории Вейерштрасса.

Формальные степени ряды можно складывать и умножать. Пусть, кроме ряда $\alpha(x)$ (см. (12)), дан формальный

14

степенной ряд
$$\beta(z) = b_0 + b_1z + b_2z^2 + \dots + b_nz^n + \dots$$
(13)

Тогда сумма и произведение этих рядов определяются по естественным формулам:
$$\alpha(z) + \beta(z) = (a_0 + b_0) + (a_1 + b_1)z + \dots + (a_n + b_n)z^n + \dots,$$
$$\alpha(z) \cdot \beta(z) = a_0b_0 + (a_1b_0 + a_2b_1)z + (a_0b_2 + a_1b_1 + a_2b_0)z^2 + \dots$$
(14)
(эти действия выполняются по правилам, аналогичным обычным правилам сложения и умножения конечных многочленов). Заметим, кстати, что обычный многочлен можно считать частным случаем формального степенного ряда — именного такого, у которого все коэффициенты, начняя с некоторого, равны нулю. При этом обчное сложение и умножение многочленов будут, конечно, совпадать с их сложением и умножением как формальных степенных рядов.

Далее, формальные степенные ряды можно дифференцировать и интеррировать. По определению
$$\frac{d}{d(z)} (\alpha(z)) = (\alpha(z))' = a_1 + 2a_2z + 3a_3z^2 + \dots + na_nz^{n-1} + \dots,$$
$$\int \alpha(z) = \int_0^z \alpha(x)dx = a_0z + \frac{a_1}{2}z^2 + \frac{a_2}{3}z^3 + \dots + \frac{a_n}{n+1}z^{n+1} + \dots$$

Для определенных таким образом сложения и умножения бесконечных рядов будут выполняться свойства, аналогичные свойства чисел или многочленов. Именно, будут выполняться переместительный, сочетательный и распределительный законы.

Подобно целым числом, из любого формального ряда можно вычесть любой другой ряд и получить опять же формальное степенной ряд. Деление же в области формального степенных рядов не всегда возможно, так же как не всегда возможно деление двух целых чисел. Например, нельзя делать на «нуль», то есть нельзя делать на ряд
$$0 = 0 + 0 \cdot z + 0 \cdot z^2 + \dots + 0 \cdot z^n + \dots$$
Нельзя осуществить деление «единиц», то есть ряд
$$1 = 1 + 0 \cdot z + 0 \cdot z^2 + \dots + 0 \cdot z^n + \dots$$
на ряд
$$z = 0 + 1 \cdot z + 0 \cdot z^2 + \dots + 0 \cdot z^n + \dots$$

Действительно, предположим, что существует ряд
$$\alpha(z) = a_0 + a_1z + a_2z^2 + \dots,$$
для которого $\alpha(z) \cdot z = 1$, или,
$$\left(a_0 + a_1z + a_2z^2 + \dots\right) \times \left(0 + 1 \cdot z + 0 \cdot z^2 + \dots\right) = 1 + 0 \cdot z + 0 \cdot z^2 + \dots$$

Но из формулы (14) следует тогда, что $a_0 \cdot 0 = 1$, что безусловно невозможно.

Аналогично доказывается, что $\alpha(z) = a_0 + a_1z + a_2z^2 + \dots$ делится на $z^n$ тогда и только тогда, когда $a_0 = a_1 = a_2 = \dots = a_{n-1} = 0$.

Легко проверить, что 1 делится на $\alpha(z)$, если только $a_0 \neq 0$, причем коэффициенты получаются ряда определения однозначно.

Найдем, для примера, результат деления «единиц» на ряд 1—z. Пусть $(1-z)(a_0 + a_1z + a_2z^2 + \dots) = 1 + 0 \cdot z + 0z^2 + \dots$

Тогда, раскрывая скобки и приравнивая коэффициент при одинаковых степенях $z$, получаем систему равенств
$$1 \cdot a_0 = 1, a_1 - a_0 = 0, a_2 - a_1 = 0, \dots, a_n - a_{n-1} = 0, \dots,$$
откуда $a_0 = a_1 = \dots = a_n = \dots = 1$, то есть
$$\frac{1}{1-z} = 1 + z + z^2 + z^3 + \dots + z^n + \dots$$

Мы уже пользовались этой формулой (см. (3) выше и сноку на с. 10) под другим названием; здесь же эта формула — верное равенство для формальных степенных рядов (и условие $|z| < 1$ уже не причем).

Бесконечные суммы и произведение

В решении задач в начале исследования бесконечные произведения; не менее полезны и бесконечные суммы (в частности, формальный степенной ряд можно рассматривать как бесконечную сумму однозначнов). Во избежание непрятности, даим необходимые определения этих понятий.

Пусть $\alpha_1(z), \alpha_2(z), \dots, \alpha_k(z), \dots$ — последовательность формальных степенных рядов (в частности — многочленов). Мы хотим определить бесконечную сумму и бесконечное произведение:
$$\left(\alpha_1(z)\right) + \left(\alpha_2(z)\right) + \dots + \left(\alpha_k(z)\right) + \dots,$$
(15)
$$\left(\alpha_1(z)\right) \cdot \left(\alpha_2(z)\right) \cdot \dots \cdot \left(\alpha_k(z)\right) \cdot \dots$$
(16)

так же, как и выше, то есть с помощью раскрытия скобок и приведения подоб-

15

ных членов. Однако такое определение в общем случае не годится. Действительно, если, например, в «бесконечном произведении»

$$(1+z)(1+z) \cdot \dots \cdot (1+z) \cdot \dots$$

мы начнем раскрывать скобки и прибодить подобные, мы сразу увидим, что коэффициент, скажем, при $z^2$, растет и продолжает расти по мере того, как мы раскрываем скобки. Этот пример прициплально отличается от ранее разобранного произведения

$$(1+z)(1+z^2)(1+z^4) \cdot \dots$$

$$\dots \cdot (1+z^{2m}) \cdot \dots$$

в котором начальные коэффициенты постепенно ставили и руются, в силу того, что в «далеких» скобках нет одночленов с формальной переменной в «низкой» степени.

Так вот, бесконечная сумма (15) и бесконечное произведение (16) определяются, только если произходит стабилизация коэффициентов при раскрытии скобок и приведении подобных членов, — как формальный степенной ряд с полученными таким образом коэффициентами.

Точно определение «стабилизации» такое: для всякого натурального $d$ найдется натуральное число $n$ такое, что при $n \geq N$ ряд $a_n(z)$ не содержит $z$ в степенях меньше, чем $d$.

Этим завершается наш краткий экскурс в теории формальных степенных рядов. Мы советуем читателю превать чтение на этом месте, вернуть к примерам в начале статьи и убедиться в том, что в них производились не комнютельные трики с бесконечными многочленами, а в полне законные операции с формальными степенными рядами.

Производящие функции

Вдумчивый читатель, разбиая примеры в начале статьи, возможно, заметил, что успex метода связан с возможностью записать производящий функцию формального степенного ряда $a(z)$ в компактном виде. Так, например, производящий функцию последовательности 1, 1, 1, … можно записать как $1/(1-z)$, либо

$$\frac{1}{1-z} = 1+z+z^2+\dots+z^n+... \tag{17}$$

Отправляясь от этого соответствия, можно получить много других конкретичных производящих функций. Например, умножив обе части (17) на $z$ и дифференциру, получим

$$\left( \frac{z}{1-z} \right)' = 1+2z+3z^2+\dots+(n+1)z^n+... \tag{18}$$

Это значит, что функция $(z(1-z))' = 1/(1-z)^2$ является производящей для последовательности 1, 2, 3, 4, ….

Снова умножая на $z$ и дифференциру, мы получим

$$\frac{1+z}{(1-z)^3} = 1+2^2z+3^2z^2+\dots+(n+1)^2z^n+... \tag{19}$$

Мы нашли явное выражение для производящей функции последовательности $1^2, 2^2, 3^2, 4^2$, …

Читатели, умелошие делить многочлены «уголком», могут получить соответствие (19) иначе — именно деля многочлен $1+z$ на многочлен $1-3z+3z^2-z^3$.

Вновь отправляясь от (17), но теперь уже интегриру, получим

$$\int_0^z \frac{dx}{1-x} = \int_0^1 dx + \int_0^z xdx + \dots + \int_0^z x^ndx + \dots,$$

$$-\ln(1-z) = z + \frac{z^2}{2} + \frac{z^3}{3} + \dots$$

Мы видим, что производящей функции последовательности 1, 1/2, 1/3, … будет функция $-\ln(1-z)/z$.

Ограничимся этим примерами и перейдем к задачам, решаемым методом производящих функций.

Задачи

1. Докажите, что любое целое положительное число можно представить в двойной записи единственным образом.

Указание. Сравните эту задачу с задачей о взвешивании.

2. Докажите, что любое целое положительное число можно представить в десятичной записи единственным образом.*

Указание. Воспользоваться соответствием (доказав его):

$$\left( 1+z+z^2+\dots+z^9 \right) \cdot \left( 1+z^{10}+z^{20}+...+z^{90} \right) \times \left( 1+z^{100}+z^{200}+...z^{900} \right) \cdot \dots = 1+z+z^2+z^3+\dots=1/(1-z).$$

3. Докажите, что любое целое положительное в виде суммы различных чисел положительных слагаемых. (Например, для числа 6 — четые способа, имеющего $6=1+5=2+4=1+2+3$ и $1+5=3+3=1+1+1+3=1+1+1+1+1+1$.)

(Окончание см. на с. 52)

*) То, что этот факт вам известен с первого класса, нельзя считать математическим обоснованием его справедливости!