2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Таблица производящих функций
Сообщение25.12.2011, 20:03 


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

Рассматривается последовательность чисел $(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 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Таблица производящих функций
Сообщение26.12.2011, 12:51 
Заслуженный участник


26/07/09
1559
Алматы

(2migmit)

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

 Профиль  
                  
 
 Re: Таблица производящих функций
Сообщение26.12.2011, 15:21 
Заслуженный участник


10/08/09
599
Circiter в сообщении #520019 писал(а):

(2migmit)

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

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

 Профиль  
                  
 
 Re: Таблица производящих функций
Сообщение26.12.2011, 15:27 
Заслуженный участник
Аватара пользователя


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

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

(Оффтоп)

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

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


26/01/10
959
migmit в сообщении #519967 писал(а):
Ну, начнём с того, что производящие функции бывают не только вида $\sum a_nx^n$...

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

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

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

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

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

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

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


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

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

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


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

 Профиль  
                  
 
 Re: Таблица производящих функций
Сообщение02.01.2012, 17:13 
Заслуженный участник
Аватара пользователя


27/04/09
27145
Когда я смотрел, не заметил. :oops:

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


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

 Профиль  
                  
 
 Re: Таблица производящих функций
Сообщение03.01.2012, 07:11 


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

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

 Профиль  
                  
 
 Re: Таблица производящих функций
Сообщение03.01.2012, 15:38 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Таблица производящих функций
Сообщение03.01.2012, 16:35 


26/01/10
959
Someone в сообщении #522574 писал(а):
Да может и пригодиться. Но там бы как-нибудь исправить эти странные $\sum n$ и $\sum n^2$...

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 13 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group