Введение
Метод рекуррентных соотношений позволяет решать многие комбинаторные
задачи. Но в целом ряде случаев рекуррентные соотношения довольно трудно
составить, а еще труднее решить. Зачастую эти трудности удается обойти,
использовав производящие функции. Поскольку понятие производящей функции связано с
бесконечными степенными рядами, познакомимся с этими рядами.
Деление многочленов
Если заданы два многочлена $$f(x)$$ и $$\varphi (x)$$, то
всегда существуют многочлены $$q(x)$$ ( частное )
и $$r(x)$$ ( остаток ),
такие, что $$f(x) = \varphi (x)q(x) + r(x)$$, причем степень $$r(x)$$ меньше степени $$\varphi (x)$$ или $$r(x) = 0$$. При этом $$f(x)$$ называется делимым,
а $$\varphi (x)$$ - делителем. Если же мы хотим, чтобы деление выполнялось без остатка,
то придется допустить в качестве частного не только многочлены, но и бесконечные
степенные ряды. Для получения
частного надо расположить многочлены по возрастающим степеням $$x$$ и
делить "углом", начиная с младших членов. Рассмотрим, например, деление $$1$$ на $$1 - x$$$$\arraycolsep=0pt
\begin{array}{rrrrl}
1 \multicolumn{1}{|l}{1-x}\\
\cline{5-5}
\mp1{}\pm x \multicolumn{1}{|l}{1+x+x^2+\ldots}\\
\cline{1-4} x \\
{}\mp x \pm x^2\\
\cline{2-3}
x^2\\
\mp x^2\pm x^3\\
\cline{3-4}
x^3\hbox to 0pt{\ldots\hss}
\end{array}$$
Ясно, что процесс деления никогда не закончится ( так же, например, как при
обращении числа $$\frac{1}{3}$$ в бесконечную десятичную дробь). С помощью индукции легко
убедиться, что все коэффициенты частного равны единице. Поэтому в качестве частного получается
бесконечный ряд $$1 + x + x^2 + \ldots + x^n + \ldots$$.
Вообще, если $$f(x)$$ и $$\varphi (x)$$ - два многочлена$$f(x) = a_0 + \ldots + a_n x^n,$$
$$\varphi (x) = b_0 + \ldots + b_m x^m,$$
причем свободный член $$b_0$$ многочлена $$\varphi (x)$$
отличен от нуля, $$b_0^{} \ne 0$$, то при делении $$f(x)$$
на $$\varphi (x)$$ получается бесконечный ряд$$c_0+c_1x+\ldots+c_kx^k+\ldots$$
Лишь в случае, когда $$f(x)$$ делится без остатка на $$\varphi (x)$$, ряд (9.1) обрывается и мы получаем многочлен.
Алгебраические дроби и степенные ряды
При делении многочлена $$f(x)$$ на многочлен $$\varphi
(x)$$ мы получаем бесконечный степенной ряд. Возникает вопрос: как связан
этот ряд с алгебраической дробью $$\frac{{f(x)}}
{{\varphi (x)}}$$, то есть какой смысл можно придать записи$$\frac{{f(x)}}
{{\varphi (x)}} = c_0 + c_1 x + \ldots + c_n x^n + \ldots$$
Рассмотрим, например, разложение$$\frac{1}{{1 - x}} \cong 1 + x + x^2 + \ldots + x^n + \ldots$$
Мы не пишем здесь знака равенства, так как не знаем, какой смысл имеет стоящая
справа сумма бесконечного числа слагаемых. Чтобы выяснить это, попробуем
подставлять в обе части соотношения (9.3) различные значения $$x$$.
Сначала положим $$x = \frac{1}{{10}}$$. Тогда левая часть соотношения примет значение $$\frac{{10}}{9}$$, а правая превратится в бесконечный числовой ряд $$1+0,1+0,01+...+0.000...01+..$$.
Так как мы не умеем складывать бесконечно много слагаемых, попробуем взять
сначала одно слагаемое, потом - два, потом - три и так далее слагаемых. Мы
получим такие суммы: $$1; 1,1; 1,11; ... ; 1,111...1;$$ $$n$$. Ясно, что с возрастанием $$n$$
эти суммы приближаются к значению $$\frac{{10}}
{9} = 1,11\ldots$$, которое приняла левая часть соотношения (9.3) при $$x = \frac{1}{{10}}$$.
То же самое получится, если вместо $$x$$ подставить в обе части
(9.3) число $$\frac{1}{2}$$. Левая часть равенства примет значение 2, а правая превратится в
бесконечный числовой ряд $$1 + \frac{1}
{2} + \frac{1}
{4} + \frac{1}
{8} + \ldots + \frac{1}
{{2^n }} + \ldots$$ Беря последовательно одно, два, три, четыре,
слагаемых, мы получим числа 1; $$1\frac{1}
{2}$$ ; $$1\frac{3}
{4}$$ ; $$1\frac{7}
{8}$$,…, $$2 - \frac{1}
{{2^n }}$$. Ясно, что с возрастанием $$n$$ эти числа стремятся к
числу 2.
Однако, если взять $$x = 4$$, то левая часть (9.3) примет значение $$- \frac{1}
{3}$$, а в правой получим ряд $$1 + 4 + 4^2 + \ldots + 4^n+…$$
Если последовательно складывать члены этого ряда, то получаются суммы 1; 5;
21; 85; … Эти суммы неограниченно увеличиваются и не приближаются к числу $$- \frac{1}
{3}$$.
Мы встретились, таким образом, с двумя случаями. Чтобы их различать, введем
общее понятие о сходимости и расходимости числового ряда. Пусть задан
бесконечный числовой ряд$$a_1 + a_2 + \ldots + a_n + \ldots$$
Говорят, что бесконечный числовой ряд сходится к числу $$b$$, если разность $$b - (a_1 + a_2 + \ldots + a_n )$$
стремится к нулю при неограниченном увеличении $$n$$. Иными словами,
какое бы число $$\varepsilon > 0$$ мы ни указали, отклонение
суммы $$a_1 + \ldots + a_n$$ от $$b$$, начиная с
некоторого номера $$N$$, окажется меньше $$\varepsilon$$:$$\left| {b - (a_1 + \ldots + a_n )} \right| < \varepsilon
\text{ если }n \geqslant N.$$
В этом случае число $$b$$ называют суммой бесконечного ряда $$a_1
+ a_2 + \ldots + a_n + \ldots$$ и пишут$$b =a_1 + a_2 + \ldots + a_n + \ldots.$$
Если не существует числа $$b$$, к которому сходится данный ряд (9.4),
то этот ряд называют расходящимся.
Проведенное выше исследование показывает, что$$\frac{{10}}{9} = 1 + 0,1 + 0,01 + \ldots + 0,00\ldots 01 + \ldots,$$
$$2 = 1 + \frac{1}
{2} + \frac{1}
{4} + \ldots + \frac{1}
{{2^n }} + \ldots,$$
в то время как ряд $$1 + 4 + 16 + \ldots + 4^n +$$... расходится.
Более тщательное исследование показывает, что если $$\left| x \right|
< 1$$, то ряд $$1 + x + \ldots + x^n + \ldots$$ сходится к $$\frac{1}{{1 - x}}$$, а если $$\left| x \right| > 1$$, то он
расходится. Чтобы доказать это утверждение, достаточно заметить, что$$1 + x + \ldots x^n = \frac{{1 - x^{n + 1} }}{{1 - x}}$$
и что при $$n \to \infty$$ выражение $$x^{n + 1}$$ стремится
к нулю, если $$\left| x \right| < 1$$, и к бесконечности, если $$\left| x \right| \geqslant 1$$. При $$x = \pm 1$$
получаем расходящиеся числовые ряды $$1 + 1 + \ldots + 1 + \ldots$$
и $$1 - 1 + \ldots + 1 - 1 + \ldots$$.Итак, если $$\left| x \right| < 1$$, то$$\frac{1}
{{1 - x}} = 1 + x + \ldots + x^n + \ldots$$
Отметим, что равенство (9.5) - это известная из школьного курса математики
формула для суммы бесконечно убывающей геометрической прогрессии.
Мы выяснили, таким образом, смысл записи$$\frac{1}
{{1 - x}} = 1 + x + \ldots + x^n + \ldots.$$
Она показывает, что для значений $$x$$, лежащих в некоторой области,
а именно при $$\left| x \right| < 1$$, стоящий справа ряд
сходится к $$\frac{1}
{{1 - x}}$$. Говорят, что функция $$\frac{1}
{{1 - x}}$$ при $$\left| x \right| < 1$$ разлагается в
степенной ряд $$1 + x + \ldots + x^n + \ldots$$.Теперь уже можно выяснить и более общий вопрос.
Пусть при делении многочлена $$f(x)$$ на многочлен $$\varphi
(x)$$ получился степенной ряд$$c_0 + c_1 x + \ldots + c_n x^n + \ldots$$
Оказывается, что тогда при достаточно малых значениях $$x$$ ряд (9.6)
сходится к $$f(x)/ \varphi (x)$$. Размеры области сходимости зависят от корней
знаменателя, то есть чисел, при которых знаменатель обращается в нуль.
Именно, если эти числа равны $$x_1,\ldots,x_k$$ и $$r$$ -
наименьшее из чисел $$\left| {x_1 } \right|,\ldots,\left| {x_k } \right|$$, то ряд
сходится в области $$\left| x \right| < r$$.
Иными словами, всегда есть область $$\left| x \right| < r$$, в
которой выполняется равенство$$\frac{{f(x)}}
{{\varphi (x)}} = c_0 + c_1 x + \ldots + c_n x^n + \ldots$$
В степенные ряды можно разлагать не только алгебраические дроби, но и многие
другие функции. В математическом анализе доказывают, например, что$$\sin x = x - \frac{{x^3 }}{{3!}} + \frac{{x^5 }}{{5!}} - \ldots,$$
$$\cos x = 1 - \frac{{x^2 }}{{2!}} + \frac{{x^4 }}{{4!}} - \ldots,$$
$$e^x = 1 + x + \frac{{x^2 }}{{2!}} + \frac{{x^3 }}{{3!}} + \ldots.$$
Отметим еще следующее важное утверждение: функция $$f(x)$$
не может иметь двух различных разложений в степенные ряды.
Действия над степенными рядами
Перейдем теперь к действиям над степенными рядами. Пусть функции $$f(x)$$ и $$\varphi (x)$$ разложены в степенные ряды$$f\left( x \right) = a_0 + a_1 x + \ldots a_n x^n + \ldots$$
$$\varphi (x) = b_0 + b_1 x + \ldots b_n x^n \ldots$$
Тогда$$f(x) + \varphi (x) = (a_0 + a_1 x + \ldots a_n x^n + \ldots )+(b_0 + b_1 x
+ \ldots b_n x^n \ldots ).$$
Оказывается, что слагаемые в правой части равенства можно переставить и
сгруппировать вместе члены с одинаковыми степенями $$x$$. Это утверждение
совсем не так очевидно, как кажется на первый взгляд. Ведь в
правой части равенства у нас бесконечные суммы, а в бесконечных суммах
переставлять слагаемые можно далеко не всегда. После этой
перегруппировки мы получим$$f(x) + \varphi (x) = (a_0 + b_0 ) + (a_1 + b_1 )x + \ldots + (a_n + b_n
)x^n + \ldots$$
Ряд, стоящий в правой части равенства (9.14), называется суммой степенных рядов (9.12) и (9.13).
Посмотрим теперь, как разлагается в степенной ряд произведение функций $$f(x)$$ и $$\varphi (x)$$. Мы имеем$$f(x)\varphi (x) = (a_0 + a_1 x + \ldots a_n x^n + \ldots ) \times (b_0 +
b_1 x + \ldots b_n x^n \ldots ).$$
Оказывается, что как и в случае многочленов, ряды, стоящие в правой части
равенства (9.15), можно почленно перемножать. Мы опускаем доказательство этого
утверждения. Найдем ряд, получающийся после почленного перемножения. Свободный член этого
ряда равен $$a_0 b_0$$. Члены, содержащие $$x$$, получатся
дважды: при умножении $$a_0$$ на $$b_1 x$$ и при умножении $$a_1^{} x$$ на $$b_0$$. Они дают$$a_0^{} b_1 x + a_1 b_0 x = (a_0 b_1 + a_1 b_0 )x.$$
Точно так же вычисляются члены, содержащие $$x^2$$. Таким образом,$$f(x)\varphi (x) =
a_0 b_0 + (a_0 b_1 + a_1 b_0 )x + \ldots + (a_0 b_n + \ldots + a_n b_0
)x^n + \ldots$$
Ряд, стоящий в правой части равенства (9.16), называется произведением рядов (9.12) и (9.13).
В частности, возводя ряд (9.12) в квадрат, получаем$$f^2 (x) = a_0^2 + 2a_0^{} a_1 x + (a_1^2 + 2a_0 a_2 )x^2 + 2(a_0 a_3^{} +
a_1 a_2 )x^3 + \ldots$$
Посмотрим теперь, как делят друг на друга степенные ряды. Пусть свободный
член ряда (9.13) отличен от нуля. Покажем, что в этом случае существует такой
степенной ряд$$c_0+c_1x+\ldots+c_nx^n+\ldots,$$
что$$(b_0 + b_1 x + \ldots + b_n x^n + \ldots ) \times (c_0^{} + c_1 x + \ldots
+ c_n x^n + \ldots ) =\\= a_0 + a_1 x + \ldots + a_n x^n + \ldots$$
Для доказательства перемножим ряды в левой части этого равенства. Мы
получим ряд$$b_0 c_0 + (b_0 c_1 + b_1 c_0 )x + \ldots + (b_0 c_n + \ldots + b_n c_0
)x^n + \ldots$$
Для того чтобы этот ряд совпадал с рядом (9.12), необходимо и достаточно, чтобы
выполнялись равенства$$b_0 c_0 = a_{\begin{subarray}{l}
0 \\
\end{subarray}},$$
$$b_0 c_1 + b_1 c_0 = a_1,$$
$$..........$$
$$b_0 c_n + \ldots + b_n c_0 = a_n,$$
$$..........$$
Эти равенства дают бесконечную систему уравнений для отыскания коэффициентов
Из первого уравнения системы получаем $$c_0 = \frac{{a_0 }}
{{b_0 }}$$. Подставим полученное значение во второе уравнение. Мы получим
уравнение$$b_0 c_1 = a_1 - \frac{{b_1 a_0 }}{{b_0 }},$$
из которого находим, что $$c_1 = \frac{{a_1 b_0 - b_1 a_0 }}
{{b_0^2 }}$$. Вообще, если уже найдены коэффициенты $$c_0,\ldots,c_{n
- 1}$$, то для отыскания $$c_n$$ имеем уравнение$$b_0 c_n = a_n - b_1 c_{n - 1} - \ldots - b_n c_0.$$
Это уравнение разрешимо, поскольку $$b_0 \ne 0$$.Итак, мы доказали существование
ряда (9.18), удовлетворяющего соотношению
(9.19). Ряд (9.18) называют частным при делении рядов (9.12) и (9.13). Можно
доказать, что он получается при разложении функции $$f(x)/\varphi
(x)$$. Таким образом, степенные ряды можно складывать, умножать и делить
(последнее - при условии, что свободный член делителя отличается от нуля). Эти действия
соответствуют действиям над разлагаемыми функциями.
