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

[Zealint]

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

Рассматривается последовательность чисел $(a_n)$, записанная в виде $(a_0,a_1, a_2,\ldots)$. Ниже приводится таблица некоторых простых последовательностей и соответствующих им производящих функций, вполне покрывающих набор необходимых для студента знаний, к которым оный обращается в процессе решения упражнений.

Все суммы $\sum$, если не оговорено иное, берутся по $n$ от 0 до $\infty$.

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

[ Обратиться к автору таблицы вопросами (в случае вероятного отсутствия его на форуме) можно посредством указанной ссылки ]

$$ \begin{tabular}{|r|l|l|l|} \hline \multirow{}{}{\No} & \multirow{}{}{Последовательность} & \multicolumn{2}{c|}{Производящая функция} \\ \cline{3-4} & & в виде ряда & в замкнутом виде \\ \hline & & & \\ 1 & $(1,0,0,\ldots)$ & $\displaystyle1$ & $\displaystyle1$ \\ & & & \\ 2 & $(\underbrace{0,0,\ldots,0}_{\displaystyle m\mbox{\small{} нулей}},1,0,0,\ldots)$ & $\displaystyle z^m$ & $\displaystyle z^m$ \\ & & & \\ 3 & $(1,1,1,\ldots)$ & $\displaystyle\sum z^n$ & $\displaystyle\frac{1}{1-z}$ \\ & & & \\ 4 & $(1,-1,1,-1,\ldots)$ & $\displaystyle\sum (-1)^nz^n$ & $\displaystyle\frac{1}{1+z}$ \\ & & & \\ 5 & $(\underbrace{1,0,0,0}_{\displaystyle m\mbox{\small{} чисел}},1,0,\ldots)$ & $\displaystyle\sum z^{mn}$ & $\displaystyle\frac{1}{1-z^m}$ \\ & & & \\ 6 & $(1,2,3,4,\ldots)$ & $\displaystyle\sum (n+1)z^{n}$ & $\displaystyle\frac{1}{(1-z)^2}$ \\ & & & \\ 7 & $(1,2,4,8,16,\ldots)$ & $\displaystyle\sum 2^nz^{n}$ & $\displaystyle\frac{1}{1-2z}$ \\ & & & \\ 8 & $(1,r,r^2,r^3,\ldots)$ & $\displaystyle\sum r^nz^{n}$ & $\displaystyle\frac{1}{1-rz}$ \\ & & & \\ 9 & $\left(\binom{m}{0},\binom{m}{1},\binom{m}{2},\binom{m}{3},\ldots\right)$ & $\displaystyle\sum \binom{m}{n}z^{n}$ & $\displaystyle(1+z)^m$ \\ & & & \\ 10 & $\left(1,\binom{m}{1},\binom{m+1}{2},\binom{m+2}{3},\ldots\right)$ & $\displaystyle\sum \binom{m+n-1}{n}z^{n}$ & $\displaystyle\frac{1}{(1-z)^m}$ \\ & & & \\ 11 & $\left(1,\binom{m+1}{m},\binom{m+2}{m},\binom{m+3}{m},\ldots\right)$ & $\displaystyle\sum \binom{m+n}{m}z^{n}$ & $\displaystyle\frac{1}{(1-z)^{m+1}}$ \\ & & & \\ 12 & $\left(0,1,\frac{1}{2},\frac{1}{3},\ldots\right)$ & $\displaystyle\sum_{n\geq1} \frac{1}{n}z^{n}$ & $\displaystyle\ln\frac{1}{1-z}$ \\ & & & \\ 13 & $\left(0,1,-\frac{1}{2},\frac{1}{3},-\frac{1}{4},\ldots\right)$ & $\displaystyle\sum_{n\geq1} \frac{(-1)^{n+1}}{n}z^{n}$ & $\displaystyle\ln(1+z)$ \\ & & & \\ 14 & $\left(1,1,\frac{1}{2},\frac{1}{6},\frac{1}{24},\ldots\right)$ & $\displaystyle\sum \frac{1}{n!}z^{n}$ & $\displaystyle e^z$ \\ & & & \\ \hline \end{tabular} $$

[migmit]

Ну, начнём с того, что производящие функции бывают не только вида $\sum a_nx^n$...

[Circiter]

(2migmit)

Вы в последний столбец смотрели?

[migmit]

Circiter в сообщении #520019 писал(а):

(2migmit)

Вы в последний столбец смотрели?

Вы, видимо, не поняли. Речь не о том, что производящую функцию можно ЗАПИСАТЬ в другом виде. Речь о том, что сами производящие функции бывают другие. Например, довольно полезной является биномиальная производящая функция $\sum\frac{a_nx^n}{n!}$. Есть и другие, и много разных.

[arseniiv]

Ну так в чём проблема, можно отдельно сделать таблицы для других! Отдельно лучше потому, что в одной таблице они друг другу будут мешать, и всё равно не используются в одном и том же расчёте.

-- Пн дек 26, 2011 18:31:02 --

(Оффтоп)

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

[Zealint]

migmit в сообщении #519967 писал(а):

Ну, начнём с того, что производящие функции бывают не только вида $\sum a_nx^n$...

Не надо с этого начинать. Я же написал, что

Цитата:

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

Если у вас есть уникальная программа учебно-методического комплекса, в которую входят и другие производящие функции, я не мешаю сделать аналогичную таблицу таковых. И таблицу производящих функций моментов, а также функций нескольких переменных. Согласен с тем, что вы, видимо, хотели сказать между строк: название темы выбрано неудачно.

Цитата:

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

Я бы тогда убрал из моей таблицы последнюю строку, а вместо этого сделал бы другую, в которой рассмотрены биномиальные. Название моей таблицы можно будет поменять на "Рациональные производящие функции".

Цитата:

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

Можно сделать. Попробую как смогу.

[Zealint]

Ну, вот пример таблицы преобразований, проверяйте.

-------------------------------------------------------------

Имеются две производящие функции

$$ G(z)=\sum_{n=0}^{\infty}a_n z^n \quad\mbox{ и }\quad H(z)=\sum_{n=0}^{\infty}b_n z^n $$

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

$$ \begin{tabular}{rcl} \hline &&\\ $\displaystyle\alpha G(z) + \beta H(z)$ & {}={} & $\displaystyle\sum (\alpha a_n + \beta b_n)z^n$ \\ &&\\ $\displaystyle z^m G(z)$ & {}={} & $\displaystyle \sum_{n\geq m} a_{n-m} z^n$, \quad $m\geq 0$ и целое \\ &&\\ $\displaystyle \frac{G(z)-a_0-a_1z-\cdots-a_{m-1}z^{m-1}}{z^m}$ & {}={} & $\displaystyle \sum_{n} a_{n+m} z^n$, \quad $m\geq 0$ и целое \\ &&\\ $\displaystyle G(cz) $ & {}={} & $\displaystyle\sum c^n a_n z^n$ \\ &&\\ $\displaystyle G'(z)$ & {}={} & $\displaystyle\sum (n+1) a_{n+1} z^n$ \\ &&\\ $\displaystyle zG'(z)$ & {}={} & $\displaystyle\sum n a_n z^n$ \\ &&\\ $\displaystyle \int\limits_0^z G(t)\,dt$ & {}={} & $\displaystyle\sum_{n\geq1} \frac{1}{n} a_{n-1} z^n$ \\ &&\\ $\displaystyle G(z)H(z) $ & {}={} & $\displaystyle\sum_n \Bigl( \sum_{k=0}^n a_kb_{n-k} \Bigr)z^n$ \\ &&\\ $\displaystyle \frac{1}{1-z}G(z) $ & {}={} & $\displaystyle\sum_n \Bigl( \sum_{k=0}^n a_k \Bigr)z^n$ \\ &&\\ \hline \end{tabular} $$

Примеры использования

Пример 1

Вывести производящую функцию для последовательности $(a_n)$, заданной формулой $a_n=n^2$.

Возьмём за основу последовательность $(b_n)$, для которой $b_n=1$. Производящая функция для $(b_n)$ равна $G(z)=1/(1-z)$.

Применяем правило под названием «$zG'(z)$». Первое применение даёт

$$ z\cdot\biggl(\frac{1}{1-z}\biggr)' = \frac{z}{(1-z)^2} = \sum n. $$

Второе применение даёт

$$ z\cdot\biggl(\frac{z}{(1-z)^2}\biggr)' = \frac{z+z^2}{(1-z)^3} = \sum n^2. $$

Пример 2

Вывести формулу для суммы квадратов натуральных чисел, идущих подряд:

$$ \square_n = \sum_{k=0}^{n} k^2. $$

Используем правило под названием «$\frac{1}{1-z}G(z)$» по отношению к функции из примера 1:

$$ \frac{1}{1-z}\cdot \frac{z+z^2}{(1-z)^3} = \frac{z+z^2}{(1-z)^4}. $$

Теперь разложим в ряд функцию

$$ \frac{1}{(1-z)^4} = \sum_{n=0}^{\infty}\binom{-4}{n}(-z)^n= \sum_{n=0}^{\infty}\binom{n+3}{n}z^n= \sum_{n=0}^{\infty}\frac{(n+1)(n+2)(n+3)}{6}z^n. $$

Применим правило под названием «$z^mG(z)$»:

$$ \frac{z}{(1-z)^4} = \sum_{n=1}^{\infty}\frac{n(n+1)(n+2)}{6}z^n= \sum_{n=0}^{\infty}\frac{n(n+1)(n+2)}{6}z^n. $$

И ещё раз:

$$ \frac{z^2}{(1-z)^4} = \sum_{n=2}^{\infty}\frac{(n-1)n(n+1)}{6}z^n= \sum_{n=0}^{\infty}\frac{(n-1)n(n+1)}{6}z^n. $$

Складывая последние две функции, получаем

$$ \frac{z+z^2}{(1-z)^4} = \sum_{n=0}^{\infty}\biggl(\frac{n(n+1)(n+2)}{6} + \frac{(n-1)n(n+1)}{6}\biggr)z^n= \sum_{n=0}^{\infty}\frac{n(n+1)(2n+1)}{6}z^n. $$

В итоге имеем формулу

$$ \square_n = \sum_{k=0}^{n} k^2 = \frac{n(n+1)(2n+1)}{6}. $$

[Zealint]

Странно. Я оставил пару ошибок, но никто не указал на них. Видимо, никого данная тема не интересует. Не нужно? - удалите тогда, мне не жалко. Действительно, это всё тривиально. В следующий раз буду только решения нерешённых ранее задач выкладывать, благо, что таковых довольно много в комбинаторике.

[arseniiv]

Когда я смотрел, не заметил.

[shwedka]

Посмотрите книжку Риордана и книжку Холла по комбинаторному анализу. Там полно производящих функций на разные случаи жизни. на если мало покажется, почитайте Рамануджана. Значительная часть его творчества-- это сочинение (и иногда угадывание) производящих функций.

[Zealint]

shwedka в сообщении #522360 писал(а):

Посмотрите книжку Риордана и книжку Холла по комбинаторному анализу. Там полно производящих функций на разные случаи жизни. на если мало покажется, почитайте Рамануджана. Значительная часть его творчества-- это сочинение (и иногда угадывание) производящих функций.

Проблема не в том, много мне или мало этих функций, так как при желании я и сам насочиняю. Я просто сделал такую таблицу, чтобы она могла пригодиться кому-то. Не более того. В справочном разделе есть другие таблицы - по тригонометрии, например.

[Someone]

Да может и пригодиться. Но там бы как-нибудь исправить эти странные $\sum n$ и $\sum n^2$...

[Zealint]

Someone в сообщении #522574 писал(а):

Да может и пригодиться. Но там бы как-нибудь исправить эти странные $\sum n$ и $\sum n^2$...

Отлично, что отыскали ошибку. Исправить, конечно, я не могу, но уверен, что если модераторы решат скопировать таблицу в раздел со справочником, они сами всё исправят. Дописать там $z^n$ не составит труда.