3.2 Производящие функции
Основы перечислительной комбиаторики
модуль 3.2 шаг 5
Рассмотрим простейшую счетную числовую последовательность вида
\[(1,1,1,...).\]В кольце \(\mathbb{C}\left[ \left[ z \right] \right]\) формальных степенных рядов этой последовательности отвечает формальный степенной ряд вида
\[1+z+z^2+...\]| С точки зрения математического анализа такому ряду в случае $$ | z | <1 $$ отвечает функция вида |
Какая функция из математического анализа отвечает числовой последовательности вида
\[(2,5,13,...,2^n+3^n,...)?\]Пример ввода функций на Степике: функция \(3z/(1-4z)^2\) вводится как <pre>3z/(1-4z)^2</pre>.
Решение
\[\displaylines{ \sum_{n=0}^{\infty}\left(2^n+3^n \right)\cdot{z^n}=\sum_{n=0}^{\infty}(2z)^n+\sum_{n=0}^{\infty}(3z)^n= \\ =(1+2z+(2z)^2+...)+(1+3z+(3z)^2+...)= \\ = \frac{1}{1-2z}+\frac{1}{1-3z} }\]Ответ
(2-5*z)/((1-2*z)*(1-3*z))
модуль 3.2 шаг 8
Пусть \(f(z)\) есть обыкновенная производящая функция для счетной числовой последовательности
\[(a_0,a_1,a_2,...).\]Производной обыкновенной производящей функции
\[f(z)=a_0+a_1z+a_2z^2+...,\]называется формальный степенной ряд
\[g(z):=f^{'}=a_1+2a_2z+3a_3z^2+...+na_nz^{n-1}+...\]Такой ряд отвечает счетной числовой последовательности
\[(a_1,2a_2,3a_3,...,na_n,...).\]Заметим, что любая функция из математического анализа, представимая в окрестности точки \(z=0\) в виде степенного ряда
\[f(z)=a_0+a_1z+a_2z^2+...,\]дифференцируется по тому же самому правилу, что и формальный степенной ряд. Так, если забыть про формальные степенные ряды и продифференцировать функцию
\[f(z)=1+z+z^2+...=\frac{1}{1-z}\]по \(z\) то мы получим функцию
\[f^{'}=1+2z+3z^2+...=\left(\frac{1}{1-z} \right)^{'}=\frac{1}{(1-z)^2},\]отвечающую с точки зрения формальных степенных рядов числовой последовательности
\[(1,2,3,...).\]В этом случае говорят, что производящая функция \(g(z)=f^{'}(z)\) для числовой последовательности \((1,2,3,...)\) выражена через элементарную функцию \((1−z)\).
Используя описанный подход, выразить через элементарную функцию \((1−z)\) производящую функцию для числовой последовательности
\[(1^2,2^2,3^2,...).\]Решение
Если \(f^{'}(z)=1+2z+3z^2+...\) домножить на \(z\) и взять производную, то получим \(1+4z+9z^2+16z^3+...\). С другой стороны \(f^{'}(z)=\frac{1}{(1-z)^2}\), так что теперь уже это домножаем на \(z\) и берём производную: \(\left( \frac{z}{(1-z)^2} \right)^{'}=\frac{1+z}{(1-z)^3}\).
Ответ
(1+z)/(1-z)^3
модуль 3.2 шаг 13
Пусть \(f(z)\cdot{g(z)}=h(z)\), где \(h(z)=1+3z, \quad g(z)=1-z-6z^2\). Найти коэффициенты \(a_n\) функции \(f(z)\).
Решение
Ответ
1.2*3^n-0.2*(-2)^n