Тема 5.3. Метод производящих функций

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

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

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

Пример 5.2: Найти число сочетаний из по с повторениями, т.е.

Решение: Для имеем следующее рекуррентное соотношение

Для того чтобы равенство имело место и при достаточно считать, что .

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

Умножим обе части равенства и сложим почленно все равенства, тогда получим

, но

,

и, подставляя эти значения, имеем

, откуда следует

Так как , то

следовательно, . Из теории степенных рядов известно, что

значит, из единственности разложения функции в ряд Маклорена, следует .

Дата добавления: 2015-10-28