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

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

Определение

Напоминаю, что мы находимся в рамках определения, данного во «Введении», а именно: производящая функция последовательности (a0, a1, a2, ...) есть формальный степенной ряд

\begin{displaymath} G(z)=\sum_{n=0}^{\infty} a_nz^n = a_0+a_1z+a_2z^2+\cdots. \end{displaymath}

Говорят, что функция «производит», или «генерирует» последовательность, так как в разложении функции G(z) ряд по степеням z, коэффициент при zn равен an. Обозначается этот факт с помощью записи:

\begin{displaymath}[z^n]G(z) = a_n. \end{displaymath}

Данная запись так и читается: «коэффициент при zn в разложении функции G по степеням z».

Последовательность (an) начинается от нуля, но иногда удобно считать, что n — произвольное целое число. Для этого полагаем a-1=a-2=...=0.

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

\begin{displaymath} G(z) = \sum_{n=0}^{\infty}n!z^n = 1+ z+ 2z^2 + 6z^3+24z^4+120z^5+\cdots, \end{displaymath}

однако манипуляции с ними остаются корректными все равно. Строгое доказательство преобразований формальных степенных рядов здесь не приводится.

В любом случае, если Вы не доверяете механизму производящих функций, можно поступить следующим образом: получить некоторую формулу, а затем доказать её строго другим способом, например, методом математической индукции. Скажем, получили формулу для чисел Фибоначчи — проверьте, что она удовлетворяет рекуррентному соотношению и выполняются начальные условия. Проще доказать формулу, которая уже у нас в руках, чем выводить её «с нуля».

Сдвиг

Итак, функция G(z) генерирует последовательность (a0, a1, a2, ...). Что даёт умножение всей функции на zm (m≥0, целое)? Для ответа на этот вопрос распишем процесс умножения подробнее:

\begin{displaymath} z^mG(z)=z^m\sum_{n=0}^{\infty} a_nz^n = a_0z^m+a_1z^{m+1}+a_2{z^{m+2}}+\cdots. \end{displaymath}

Данная функция генерирует новую последовательность:

\begin{displaymath} (\underbrace{0,0,\ldots,0}_m,a_0, a_1, \ldots), \end{displaymath}

которая является сдвигом исходной последовательности на m элементов вправо. То есть

\begin{displaymath}[z^n]\Bigl( z^mG(z) \Bigr) = a_{n-m}. \end{displaymath}

Обратите внимание на то, что запись корректна, поскольку при n<m получаются отрицательные индексы, а элементы с такими индексами мы договорились считать нулями.

Аналогично, но в обратную сторону, происходит процесс деления. Для того, чтобы отрицательные (после сдвига) члены были равны нулю, нужно вычесть первые m слагаемых:

\begin{displaymath} \frac{G(z)-a_0-a_1z-\cdots-a_{m-1}z^{m-1}}{z^m} = a_m+a_{m+1}z^{}+a_{m+2}{z^{2}}+\cdots. \end{displaymath}

То есть

\begin{displaymath}[z^n]\Biggl( \frac{G(z)-a_0-a_1z-\cdots-a_{m-1}z^{m-1}}{z^m} \Biggr) = a_{n+m}. \end{displaymath}

Полиномиальный множитель и делитель

Довольно часто приходится иметь дело с последовательностью (nan). Такая последовательность получается путём дифференцирования функции G(z) с последующим умножением результата на z:

\begin{displaymath} zG'(z) = z\left(\sum_{n=0}^{\infty}a_nz^n\right)' = z\sum_{n=1}^{\infty}na_nz^{n-1} = \sum_{n=0}^{\infty}na_nz^{n} \end{displaymath}

В предпоследней сумме индекс суммирования стал начинаться от 1, так как производная константы a'0=0, а в последней сумме мы снова заставили его начинаться от 0, так как при n=0 величина (0⋅a0z0) все равно равна нулю и не влияет на сумму. Таким образом,

\begin{displaymath}[z^n]\Bigl( zG(z) \Bigr) = na_{n}. \end{displaymath}

Аналогично, интегрирование функции (G(z)−a0)/z поделит общий член последовательности на n (заметьте, что мы предусмотрительно сдвинули элементы влево, а иначе у нас получилась бы последовательность (an−1/n)n≥1 [проверьте]).

\begin{displaymath} \int\limits_0^z \frac{G(t)-a_0}{t} dt = \int\limits_0^... ...-1} \right ) dt = \sum_{n=1}^{\infty}\frac{a_n}{n}z^{n}. \end{displaymath}

Обратите внимание, что в новой последовательности нулевой член равен нулю.

\begin{displaymath}\displaylines{ [z^n] \biggl( \int\limits_0^z \frac{g(t)-a_0... ...0^z g(t) dt \biggr) = \frac{a_{n-1}}{n}, \quad n\geq 1. } \end{displaymath}

Сложение и умножение на константу

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

\begin{displaymath}\displaylines{ G(z) = \sum_{n=0}^{\infty}a_nz^n = a_0+a_1z+... ..._{n=0}^{\infty}b_nz^n = b_0+b_1z+b_2z^2+b_3z^3 + \cdots. } \end{displaymath}

Мы можем их формально сложить:

\begin{displaymath} G ( z ) + H(z) = a_0+b_0+(a_1+b_1)z+( a_2+b_2 )z^2+ \cdots = \sum_{n=0}^{\infty}(a_n+b_n)z^n, \end{displaymath}

что, в общем-то не удивительно.

Производящую функцию можно умножить на постоянный множитель:

\begin{displaymath} \alpha G ( z ) = \alpha a_0+\alpha a_1 z+ \alpha a_2 z^2 + \cdots = \sum_{n=0}^{\infty}\alpha a_nz^n. \end{displaymath}

Символ z также можно умножить на постоянное число:

\begin{displaymath} G ( rz ) = a_0+ a_1 rz+ a_2 (rz)^2 + \cdots = \sum_{n=0}^{\infty}r^n a_n z^n. \end{displaymath}

Таким образом,

\begin{displaymath}\displaylines{ [z^n] \Bigl( G(z)+H(z) \Bigr) = a_{n}+b_n,\c... ...\alpha a_{n},\cr [z^n] \Bigl( G(rz) \Bigr) = r^na_{n}. } \end{displaymath}

Свёртка

Перемножим производящие функции G(z) и H(z):

\begin{displaymath} F = G\cdot H = a_0b_0+(a_0b_1+a_1b_0)z+( a_0b_2 + a_1b_1+ ... ...um_{n=0}^{\infty}\Biggl( \sum_{k=0}^n a_kb_{n-k} \Biggr)z^n. \end{displaymath}

Сумму, взятую в скобки, принято называть «свёрткой» (обозначим её через cn):

\begin{displaymath} c_n = \sum_{k=0}^n a_kb_{n-k}. \end{displaymath}

Таким образом, произведение производящих функций, генерирующих последовательности (an) и (bn), генерирует свёртку (cn).

Рассмотрим частный случай этого замечательного факта. Пусть bn=1, тогда

\begin{displaymath} F(z) = \frac{1}{1-z}G(z) = a_0 + (a_0+a_1)z + (a_0+a_1+a_2... ... = \sum_{n=0}^{\infty}\Biggl( \sum_{k=0}^n a_k \Biggr)z^n. \end{displaymath}

То есть функция G(z)/(1−z) генерирует последовательность частичных сумм исходной последовательности (an). Такое положение дел даёт нам много свободы, например, теперь легко представлять себе разложение в ряд следующих дробей, не вспоминая явно про биномиальные коэффициенты:

\begin{displaymath} \begin{array}{rcl} \displaystyle G(z)=1 & {}\Leftrightar... ... n\geq0} \\ &&\\ \ldots&\ldots&\ldots\\ \end{array} \end{displaymath}

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

Далее, используя свёртку, можно доказать некоторые полезные тождества. Мы знаем, чему равна сумма биномиальных коэффициентов с целым положительным верхним индексом n: Она равна 2n. А чему равна сумма их квадратов? —

\begin{displaymath} \sum_{k=0}^{n} \binom{n}{k}^2 =\; ?, \quad n\geq 0, \mbox { целое}. \end{displaymath}

Распишем сумму подробнее:

\begin{displaymath} \sum_{k=0}^{n} \binom{n}{k}\binom{n}{k} = \sum_{k=0}^{n} \binom{n}{k}\binom{n}{n-k}. \end{displaymath}

Теперь хорошо видно, что это свёртка двух последовательностей, каждая из которых порождается функцией

\begin{displaymath} (1+z)^n = \sum_{k=0}^{n} \binom{n}{k}. \end{displaymath}

Значит

\begin{displaymath} \sum_{k=0}^{n} \binom{n}{k}^2 = [z^n](1+z)^{2n} = \binom{2n}{n}, \quad n\geq 0, \mbox { целое}. \end{displaymath}

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

Чётные и нечётные элементы

Расмотрим сумму

\begin{displaymath} G(z) + G(-z) = \sum_{n=0}^{\infty} (a_nz^n+a_n(-z)^n) = \s... ...{\infty} a_n(1+(-1)^n)z^n=2\sum_{n=0}^{\infty} a_{2n}z^{2n}. \end{displaymath}

Таким образом, производящая функция

\begin{displaymath} \frac{G(z)+G(-z)}{2} \end{displaymath}

генерирует последовательность (a0, 0, a2, 0, a4, ...), то есть последовательность, в которой элементы с нечётными номерами заменены нулями. Например, пусть G(z)=1/(1−z), тогда

\begin{displaymath} \frac{G(z)+G(-z)}{2} = \frac12\left(\frac{1}{1-z}+\frac{1}{1+z}\right) = \frac{1}{1-z^2}. \end{displaymath}

Полученная производящая функция генерирует последовательность (1, 0, 1, 0, ...), что согласуется с таблицей производящих функций (последовательность №5 при m=2).

Последовательность, в которой элементы с нечётным индексом вырезаны, можно «уплотнить» заменой z на z1/2:

\begin{displaymath} \frac{G(\sqrt{z})+G(-\sqrt{z})}{2} = \sum_{n=0}^{\infty} a_{2n}z^n. \end{displaymath}

Такая производящая функция генерирует последовательность из элементов с чётными номерами в исходной последовательности: (a0, a2, a4, ...).

Рассуждая аналогично, получим

\begin{displaymath} \frac{G(z)-G(-z)}{2} = \sum_{n=0}^{\infty} a_{2n+1}z^{2n+1}. \end{displaymath}

Такая функция «вырезает» элементы, стоящие на чётных позициях. Вопрос: как «уплотнить» такую последовательность (убрать появившиеся нули)?

Таблица преобразований

Предполагается, что

\begin{displaymath}\displaylines{ G(z) = \sum_{n=0}^{\infty}a_nz^n = a_0+a_1z+... ..._{n=0}^{\infty}b_nz^n = b_0+b_1z+b_2z^2+b_3z^3 + \cdots. } \end{displaymath}

В таблице указаны основные преобразования, которые можно законно выполнять с производящими функциями G(z) и H(z), а также комплексными числами α, β, r и целым m. В левой колонке указано действие над функциями, а в правой — порождаемая после этого действия последовательность.

\begin{displaymath} \begin{array}{\vert rcl\vert} \hline \mbox{действие}&... ...a_1,0,a_3,0,a_4,\ldots)\\ &&\\ \hline \par \end{array} \end{displaymath}
↑ наверх ↑
вернуться к содержанию