4. Производящие функции и операции над ними.

Рассмотрим бесконечную последовательность чисел (комплексных или действительных)

,

и образуем степенной ряд . Степенные ряды и операции над ними, как будет показано далее, являются важным инструментом в решении комбинаторных задач. Поэтому выражение

получило специальное название – производящая функция для последовательности чисел .

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

.

В действительности это выражение совсем не обязательно является функцией в привычном понимании этого слова. Более того, сумма ряда может вообще не иметь смысла.

Пусть даны две производящие функции

.

Суммой производящих функций и называется производящая функция

Произведением производящих функций и называется производящая функция

или

.

Таким образом, производящие функции, как и многочлены, можно почленно складывать и умножать.

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

Теорема 6. Пусть даны производящие функции и , причем . Тогда существует такая производящая функция

=, что

() ()= (7)

Следствие. Пусть свободный член ряда

отличен от нуля. Тогда существует единственный формальный степенной ряд

такой, что .

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

называется производящая функция

а интегралом – функция

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

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

,

,

(формула интегрирования по частям).

Рассмотренные операции являются эффективным средством получения новых производящих функций из уже известных функций и поэтому широко применяются при решении самых разнообразных комбинаторных задач.

Наряду с обычными производящими функциями в комбинаторике часто используются экспоненциальные производящие функции. Так для последовательности называют выражение

, (10)

где является формальным символом.

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

,

.

Ряд

Последовательность , где

,

называется последовательностью частичных сумм ряда (отрезком ряда).

Если придать некоторое значение, то степенной ряд превратится в числовой ряд, который может либо сходиться, либо расходиться. Так, например, в точке имеем числовой ряд . Отсюда, в частности следует, что степенной ряд всегда сходится, по крайней мере, в одной точке. Множество всех , при которых ряд сходится, называется областью сходимости ряда.

На области сходимости степенного ряда (11) определена его сумма . Вычисление суммы ряда при заданном из области сходимости сводится к вычислению частичной суммы и предельному переходу .

Основная теорема о сходимости степенных рядов формулируется так. Для любого степенного ряда (11) существует такое число (в частности, ), что ряд абсолютно сходится при и расходится при . При и ряд может как сходиться, так и расходиться. Число называется радиусом сходимости ряда (11), а интервал – его интервалом сходимости (при ).

Пусть – сумма степенного ряда (11) с положительным радиусом сходимости . Тогда

(13)

при . При этом также говорят, что при функция разлагается по степеням двучлена (в степенной ряд с центром ).

Дифференцирование и интегрирование степенных рядов основывается на теореме. Пусть при , где – радиус сходимости этого ряда. Тогда функция непрерывна и дифференцируема в интервале сходимости и

(14)

. (15)

При этом оба полученных ряда имеют тот же радиус сходимости , что и ряд .

Теорема 7. Для любого действительного значения при имеет место разложение

. (16)

Ряд (16) называется при этом рядом Ньютона.

Теорема 7 позволяет строить дробно-рациональные производящие функции, которые особенно часто используются при решении комбинаторных задач.

Следствие 1.

Следствие 2.

Следствие 3.

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