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

Основная идея

Пусть есть последовательность комбинаторных чисел а_i и последовательность функций j _i (x). Рассмотрим формальный ряд:

F (x) =

F (x) называется производящей функцией (для заданной последовательности ком­бинаторных чисел a_i относительно заданной последовательности функций j _i (x).

Обычно используют j _i (x) = хⁱ или j _i (x) = xⁱ/i!.

Пример

Из формулы бинома Ньютона при у = 1 имеем:

Таким образом, (1 +х) ^п является производящей функцией для биномиальных коэффициентов.

Метод неопределенных коэффициентов

Из математического анализа известно, что если

F (x) = и F (x) =

то " i а_i = b_i (для рассматриваемых здесь систем функций j _i ).

В качестве примера применения производящих функций рассмотрим доказатель­ство следующего тождества.

ТЕОРЕМА

Доказательство

Имеем: (1 + х) ^2п = (1 + х) ^п (1 + x) ^п. Следовательно,

Приравняем коэффициент при х^п:

Дата добавления: 2014-12-27