2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

Рассматривается последовательность чисел $(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}
$$

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

 
 
 
 Re: Таблица производящих функций
Сообщение26.12.2011, 12:51 

(2migmit)

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

 
 
 
 Re: Таблица производящих функций
Сообщение26.12.2011, 15:21 
Circiter в сообщении #520019 писал(а):

(2migmit)

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

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

 
 
 
 Re: Таблица производящих функций
Сообщение26.12.2011, 15:27 
Ну так в чём проблема, можно отдельно сделать таблицы для других! Отдельно лучше потому, что в одной таблице они друг другу будут мешать, и всё равно не используются в одном и том же расчёте.

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

(Оффтоп)

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

 
 
 
 Re: Таблица производящих функций
Сообщение26.12.2011, 16:59 
migmit в сообщении #519967 писал(а):
Ну, начнём с того, что производящие функции бывают не только вида $\sum a_nx^n$...

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

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

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

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

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

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

 
 
 
 Re: Таблица производящих функций
Сообщение27.12.2011, 07:35 
Ну, вот пример таблицы преобразований, проверяйте.

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

Имеются две производящие функции
$$
		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}.
	$$

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

 
 
 
 Re: Таблица производящих функций
Сообщение02.01.2012, 17:13 
Когда я смотрел, не заметил. :oops:

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

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

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

 
 
 
 Re: Таблица производящих функций
Сообщение03.01.2012, 15:38 
Аватара пользователя
Да может и пригодиться. Но там бы как-нибудь исправить эти странные $\sum n$ и $\sum n^2$...

 
 
 
 Re: Таблица производящих функций
Сообщение03.01.2012, 16:35 
Someone в сообщении #522574 писал(а):
Да может и пригодиться. Но там бы как-нибудь исправить эти странные $\sum n$ и $\sum n^2$...

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

 
 
 [ Сообщений: 13 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group