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

В комбинаторике производя́щая фу́нкция последовательности {an} — это формальный степенной ряд

\sum_{n=0}^\infty a_n x^n.

Экспоненциальная производящая функция последовательности {an} — это формальный степенной ряд

\sum_{n=0}^\infty a_n \frac{x^n}{n!}.

Довольно часто производящая функция интересующей последовательности {an} является рядом Тейлора известной аналитической функции, и это может использоваться для изучения свойств самой последовательности. Тем не менее, следует отметить, что производящей функции не обязана соответствовать аналитическая функция.

Например, оба ряда

\sum_{n=0}^\infty (3^n)^n x^n и \sum_{n=0}^\infty (2^n)^n x^n

имеют радиус сходимости ноль, т.е. расходятся во всех точках, кроме нуля, а в нуле оба дают 1, т.е. как функции они совпадают; тем не менее, как производящие функции (т.е. формальные ряды) они различны.

Производящие функции дают возможность просто описывать многие сложные последовательности в комбинаторике, а иногда помогают найти для них явные формулы. Метод производящих функций был разработан Эйлером в 50-х годах XVIII века.

Свойства

  • (Экспоненциальная) производящая функция суммы (или разности) двух последовательностей равна сумме (или разности) соответствующих (экспоненциальных) производящих функций.
  • Если A(x)=\sum_{n=0}^\infty a_n x^n и B(x)=\sum_{n=0}^\infty b_n x^n — производящие функции последовательностей {an} и {bn}, то A(x)B(x)=\sum_{n=0}^\infty c_n x^n, где c_n = \sum_{k=0}^n a_k b_{n-k}.
  • Если A(x)=\sum_{n=0}^\infty a_n \frac{x^n}{n!} и B(x)=\sum_{n=0}^\infty b_n \frac{x^n}{n!} — экспоненциальные производящие функции последовательностей {an} и {bn}, то A(x)B(x)=\sum_{n=0}^\infty c_n \frac{x^n}{n!}, где c_n = \sum_{k=0}^n {n\choose k} a_k b_{n-k}.

Примеры

Пусть Bn есть число представлений числа n в виде k_1+k_2+\cdots+k_m, где {ki} — неотрицательные целые числа и m фиксировано, тогда

\sum_{n=0}^\infty B_nx^n=(1+x+x^2+\cdots)^m=(1-x)^{-m}

Теперь число Bn может быть найдено как коэффициент при xn в разложении (1 − x) m по степеням x. Для этого можно воспользоваться определением биномиальных коэффициентов или же непосредственно взять n раз производную в нуле:

B_n=(-1)^n {-m\choose n} = m(m+1)\cdots(m+n-1)/n! = {m+n-1 \choose n}.

Ссылки

 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home