Изменения

Перейти к: навигация, поиск

Производящие функции нескольких переменных

2438 байт добавлено, 19:22, 20 июня 2020
Многочлены Бернулли
Обычные [[Производящая функция {{Определение| Производящие функции ]] хранили одну последовательность чисел. Для задач, которые требуют больше информации применяются definition='''производящие Производящие функции нескольких переменных''' (англ. ''multivariable generating function''){{---}} обычные [[Производящая функция | производящие функции]], зависящие более, чем от одной переменной. Очень часто применяются функции от двух переменных(далее они и будут рассматриваться), которые в общем случае принимают вид :<center><tex>G(x, y) = \sum\limits_{n, k \geqslant 0} g_{n, k} x^n y^k</tex>.</center>}}
Такие последовательности удобно задавать в виде треугольника. Рассмотрим несколько примеров :
== Треугольник Паскаля ==
[[File:Pascal_triangle.png{{Определение|thumb|400px|center|Рис.<tex>1</tex>]]definition='''Треугольник Паскаля ''' (рисангл.<tex>1</tex>''Pascal's triangle''). Элементы треугольника перечисляют пути, идущие из его вершины в соответствующую клетку. Пути имеют вид ломаных, составленных из векторов единичной длины двух видов: идущих вправо{{-вниз и идущих влево-вниз. {{Теорема|statement= Числа, стоящие в треугольнике - биномиальные коэффициенты <tex> c_{n,k} = \begin{pmatrix} n \\ k \end{pmatrix}бесконечная таблица биномиальных коэффициентов<ref>[https:/tex>/ru.wikipedia.|proof= Числа, стоящие в треугольнике - биномиальные org/wiki/%D0%91%D0%B8%D0%BD%D0%BE%D0%BC%D0%B8%D0%B0%D0%BB%D1%8C%D0%BD%D1%8B%D0%B9_%D0%BA%D0%BE%D1%8D%D1%84%D1%84%D0%B8%D1%86%D0%B8%D0%B5%D0%BD%D1%82 Биномиальные коэффициенты ]<tex/ref> c_{n,k} = \begin{pmatrix} n \\ k \end{pmatrix}</tex>имеющая треугольную форму. Кратко докажем (индукция В этом треугольнике на вершине и по n) . Предположим, что числа в <tex>n</tex>-ой строчке треугольника совпадают с коэффициентами разложения многочлена <tex>(1 + s)^{n}</tex>бокам стоят единицы. Каждое число различных путей, ведущих в точку <tex>(n + 1, k)</tex>, равно сумме числа путей, ведущих в точку <tex>(n, k - 1)</tex>, и числа путей, ведущих в точку <tex>(n, k)</tex> , <tex>c_{n+1,k} = c_{n,k-1} + c_{n,k}</tex>двух расположенных над ним чисел. Поэтому число <tex>c_{n+1, k}</tex> совпадает с коэффициентом при <tex>s^k</tex> в многочлене <tex>(1+s) \cdot (1+s)^n = (1+s)^{n+1}</tex>.
}}[[File:Pascal_triangle.png|thumb|350px|right|Рис.<tex>1</tex>]]
Элементы треугольника (рис.<tex>1</tex>) перечисляют пути, идущие из его вершины в соответствующую клетку. Пути имеют вид ломаных, составленных из векторов единичной длины двух видов: идущих вправо-вниз и идущих влево-вниз.
Производящая функция может быть сопоставлена треугольнику Паскаля несколькими способами. Например, можно рассмотреть производящую функцию
<tex>\displaystyle\sum\limits_{n,k = 0}^{\infty} c_{n,k} x^k y^n = \sum\limits_{n,k = 0}^{\infty} \beginbinom{pmatrixn} n \\ {k \end{pmatrix} x^k y^n = \sum\limits_{n = 0}^{\infty}</tex><tex>\Big(\sum\limits_{k = 0}^{n} \beginbinom{pmatrixn} n \\ {k \end{pmatrix} x^k\Big) y^n = \displaystyle\sum\limits_{n = 0}^{\infty} (1 + x)^n y^n = \dfrac{1}{1 - y - xy}</tex>
[[File:Pascal_triangle_3.png|thumb|600px320px|right|Рис.<tex>2</tex>]]
Второй способ соответсвует соответствует нумерации элементов треугольника числом отрезков каждого типа на путях, ведущих в соответствующую точку (рис.<tex>2</tex>) <tex>C_{n,m} = c_{n+m, n} = \begindbinom{pmatrix} n + m \\ }{m \end{pmatrix}</tex>. Тогда производящая функция будет иметь вид
<tex>\displaystyle\sum\limits_{n,m = 0}^{\infty} C_{n, m} x^n y^m = \sum\limits_{n,m = 0}^{\infty} \beginbinom{pmatrix} n + m \\ }{m \end{pmatrix} x^n y^m = \sum\limits_{k = 0}^{\infty} </tex><tex> \Big(\sum\limits_{n + m = k} \beginbinom{pmatrix} n + m \\ }{n \end{pmatrix}x^n y^m \Big)= \displaystyle\sum\limits_{k = 0}^{\infty} (x + y)^k = \dfrac{1}{1 -x - y}</tex>
Также существует еще один способ: сопоставить треугольнику Паскаля ''экспоненциальную производящую функцию''. Экспоненциальная производящая функция отличается от обычной тем, что в качестве коэффициентов степенного ряда берутся не элементы последовательности <tex>a_n</tex>, а числа <tex>\dfrac{a_n}{n!}</tex>.
==Экспоненциальные производящие функции==
<tex>\{ \alpha_n \} \mapsto \sum\limits_{n = 0}^{\infty} a_n \alpha_n s^n</tex>
определяемую последовательностью <tex>\{ \alpha_n \}</tex>. Если в последовательности <tex>\{ \alpha_n \}</tex> отсутствуют нулевые элементы, то такое сопоставление взаимно однозначно. До сих пор мы пользовались обычными производящими функциями - , отвечающими последовательности <tex>\{ \alpha_n \} \equiv 1</tex>. В зависимости от преследуемых целей целей могут принести и другие последовательности .
{{Определение
|definition=
'''Производящие экспоненциальные функции'''(англ. ''exponential generating function'') {{- --}} функции, соответсвующие соответствующие последовательности <tex>\{ \alpha_n \} = \dfrac{1}{n!}</tex>.
}}
{{Определение
|definition=
Экспоненциальные производящие функции для целочисленных последовательностей называют '''функциями Гурвица'''(англ. ''Hurwitz function'').
}}
Чем отличаются экспоненциальные производящие функции от обычных? Посмотрим на поведение экспоненциальных производящих функций при выполнении операции над ними. Сумма ведет себя обычным образом:
<tex>\displaystyle\sum\limits_{n = 0}^{\infty} \dfrac{a_n}{n!}s^n + \sum\limits_{n = 0}^{\infty} \dfrac{b+nb_n}{n!}s^n = \sum\limits_{n = 0}^{\infty} \dfrac{(a_n + b_n)}{n!} s^n</tex>
а с произведением по-другому :
<tex>\bigg(\dfrac{a_0}{0!} + \dfrac{a_1}{1!}s + \dfrac{a_2}{2!}s^2 + \ldots\bigg)\bigg(\dfrac{b_0}{0!} + \dfrac{b_1}{1!}s + \dfrac{b_2}{2!}s^2 + \ldots\bigg) = \dfrac{a_0}{0!} \dfrac{b_0}{0!} + \bigg(\dfrac{a_0}{0!} \dfrac{b_1}{1!} + \dfrac{a_1}{1!} \dfrac{b_0}{0!}\bigg)s + \bigg(\dfrac{a_0}{0!} \dfrac{b_2}{2!} + \dfrac{a_1}{1!} \dfrac{b_1}{1!} + \dfrac{a_2}{2!} \dfrac{b_0}{0!}\bigg)s^2 + \ldots</tex>
Коэффициенты <tex>\dfrac{c_n}{n!}</tex> произведения вычисляются по формуле
<tex>c_n = \begin{pmatrix} n \\ 0 \end{pmatrix} a_0 b_n + \begin{pmatrix} n \\ 1 \end{pmatrix} a_1 b_{n - 1} + \ldots + \begin{pmatrix} n \\ n \end{pmatrix} a_0 a_n b_0</tex>
Еще одно существенное отличие экспоненциальных производящих функций от обычных наблюдается при взятии производных (и при интегрировании). Дифференцирование или интегрирование экспоненциальной производящей функции приводит к сдвигу последовательности ее коэффициентов без изменения их велечины величины:
<tex>\bigg( \dfrac{a_0}{0!} + \dfrac{a_1}{1!}s + \dfrac{a_2}{2!}s^2 + \ldots \bigg)^{'} = \dfrac{a_1}{0!} + \dfrac{a_2}{1!}s + \dfrac{a_3}{2!}s^2 + \ldots </tex>
<tex>\displaystyle\int \bigg(\dfrac{a_0}{0!} + \dfrac{a_1}{1!}s + \dfrac{a_2}{2!}s^2 + \ldots \bigg) = \dfrac{a_0}{1!}s + \dfrac{a_1}{2!}s^2 + \dfrac{a_2}{3!}s^3 + \dfrac{a_3}{4!}s^4 + \ldots </tex>
Обычная производящая функция <tex>A(s) = a_0 + a_1s + a_2s^2 + \ldots</tex> выражается через экспоненциальную <tex>\mathcal{A} B(t) = \dfrac{a_0}{0!} + \dfrac{a_1}{1!}t + \dfrac{a_2}{2!}t^2 + \ldots </tex> по формуле
<tex>A(s) = \int_int\limits_{0}^{\infty} e^{-t} \mathcal{A}B(st) dt</tex>
Действительно,
<tex>k! = \int_int\limits_{0}^{\infty} e^{-t}t^kdt</tex> Теперь можно выписать экспоненциальную производящую функцию для треугольника Паскаля: <tex>\displaystyle\sum\limits_{n, m = 0}^{\infty} \dfrac{1}{(n + m)!} \dbinom{n+m}{m} x^n y^m = \sum\limits_{n = 0}^{\infty} \dfrac{(x + y)^n}{n!} = e^{x + y}</tex> ==Многочлены Бернулли==Для начала введём операцию ''усреднения'', положив <tex>A(f(x)) = \int\limits_{x}^{x+1}f(t)dt</tex>.
Теперь можно выписать экспоненциальную производящую функцию Нетрудно заметить, что эта операция переводит многочлены в многочлены: она линейна, т.е. <tex>A(a_1f_1 + a_2f_2) = a_1A(f_1) + a_2A(f_2)</tex> для треугольника Паскаля любых постоянных <tex>a_1, a_2</tex> и любых многочленов <tex>f_1, f_2</tex>, а ее значение на мономе<ref>[https://ru.wikipedia.org/wiki/%D0%9E%D0%B4%D0%BD%D0%BE%D1%87%D0%BB%D0%B5%D0%BD Моном]</ref> <tex>x^n</tex> равно
<tex>\sum\limits_{A(x^n, m ) = 0}^{\infty} \dfrac{1}{(n (x + m1)!} \begin^{pmatrix} n + m \\ m \end{pmatrix1} - x^n y^m = \sum\limits_{n = 0+1}^{\infty} \dfrac{) / (x n+ y1)= x^n}{n!} = e^{x + y}\ldots</tex>,
==Треугольник Дика==где многоточие обозначает слагаемые, степени которых меньше <tex>n</tex>. Последняя формула показывает также, что преобразование <tex>A</tex> переводит пространство многочленов степени не выше <tex>n</tex> в себя, а значит, является линейным оператором в этом пространстве. Этот оператор обратим. Действительно, любой многочлен степени не выше <tex>n-1</tex> может быть получен в результате усреднения многочлена такой же степени, и, используя последнюю формулу, мы заключаем, что и любой многочлен степени не выше <tex>n</tex> является результатом усреднения некоторого многочлена степени не выше <tex>n</tex>. Отметим, что при усреднении степень многочлена сохраняется.
[[File:Triangle_D_2{{Определение |definition='''Многочленом Бернулли''' (англ. ''Bernoulli polynomial'') степени <tex>n</tex> называется многочлен <tex>B_n(x)</tex>, результатом усреднения которого служит моном <tex>x^n</tex>, т.png|thumb|500px|right|Рисе.<tex>3B_n(x) = A^{-1}(x^n)</tex> Представление треугольника Дика]].}}
Треугольник Дика перечисляет пути в положительном квадранте плоскости, выходящие из начала координат и составленные из векторов <tex>(1, 1)</tex> и <tex>(1, -1)</tex> (рис.<tex>3</tex>). Мы можем увидеть, что элементы <tex>d_{ij}</tex> треугольника Дика отличны от нуля в том и только том случае, если <tex>i \geqslant j </tex> и <tex>i + j</tex> четно. Обозначим через <tex>D(x, y)</tex> производящую функцию Дика двух пременныхПервые многочлены Бернулли нетрудно сосчитать:
<tex>DB_0(x, y) = \sum\limits_{i,j =0}^{\infty} d_{ij} x^i y^j1</tex>
Правило построения треугольника Дика подсказывает нам уравнение на эту производящую функцию<tex>B_1(x) = x - \dfrac{1}{2}</tex>
<tex>xyDB_2(x, y) + (D(= x,y) ^2 - D(x,0))+ \dfrac{x1}{y6} = D(x, y) - 1</tex>
Действительно, коэффициент при любом мономе <tex>B_3(x^iy^j</tex> , отличном от единичного, представляет собой сумму коэффициентов при мономах <tex>) = x^3 - \dfrac{i-13}y^{i-12}</tex> и <tex>x^{i-1}y^{j2 +1}</tex> . Функция <tex>D(x, 0) = \dfrac{1 - \sqrt{1 - 4x^2}}{2x^2}</tex> нам известна, и ряд <tex>D(x, y)</tex> находится решением линейного уравнения,
<tex>DB_4(x, y) = x^4 - 2x^3 + x^2 - \dfrac{1 }{30}</tex> <tex>B_5(x) = x^5 - \sqrtdfrac{5}{2}x^4 + \dfrac{5}{3}x^3 - \dfrac{1 }{6}x</tex> <tex>B_6(x) = x^6 - 4x3x^5 + \dfrac{5}{2} x^4 - 2xy\dfrac{1}{2x(xy2}x^2 + \dfrac{1}{42}</tex> {{Теорема| about = Экспоненциальная производящая функция для многочленов Бернулли| statement = Экспоненциальная производящая функция для многочленов Бернулли имеет вид: <tex>\mathcal{B}(x , s) = \displaystyle\sum\limits_{n=0}^{\infty}B_n(x)\dfrac{s^n}{n!} = \dfrac{s}{e^s - y1}e^{sx}</tex>.| proof = Для доказательства теоремы достаточно применить операцию усреднения к левой и правой частям равенства. С одной стороны, мы имеем: <tex>A(B(x, s)) = \displaystyle\sum\limits_{n=0}^{\infty}A(B_n(x))\dfrac{s^n}{n!} = \sum\limits_{n=0}^{\infty}x^n\dfrac{s^n}{n!} = e^{xs}</tex>. С другой стороны, имеем: <tex>A(\dfrac{s}{e^s - 1}e^{sx}) = \dfrac{s}{e^s-1}A(e^{sx}) = \dfrac{s}{e^s-1}\dfrac{1}{s}(e^{s(x+1)} - e^{sx}) = e^{sx}</tex>, и теорема доказана.}} Определим теперь ''числа Бернулли''<ref>[https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%91%D0%B5%D1%80%D0%BD%D1%83%D0%BB%D0%BB%D0%B8 числа Бернулли]</ref> как значения многочленов Бернулли в нуле. Вот начало последовательности чисел Бернулли: <tex>1, -\dfrac{1}{2}, 0, \dfrac{1}{6}, -\dfrac{1}{30}, \dfrac{1}{42}, 0, -\dfrac{1}{30}, \dfrac{5}{66}, 0, -\dfrac{691}{2730}, 0, \ldots </tex> Доказанная теорема позволяет нам легко выписать экспоненциальную производящую функцию для чисел Бернулли. Для этого достаточно подставить в экспоненциальную производящую функцию для многочленов Бернулли значение <tex>x = 0</tex>: <tex>\displaystyle\sum\limits_{n=0} B_n\dfrac{s^n}{n!} = \dfrac{s}{e^s - 1}</tex>.
==См. также==
*[[Производящая функция]]
 
==Примечания==
<references/>
==Источники информации==
* ''Ландо С.К.'' '', Лекции о производящих функциях'' . {{---}} 3-е изд., испр. {{---}} М.: МЦНМО, 2007 . {{--- С}} 57с. 57ISBN 978-5-94057-042-4
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]][[Категория: Подсчёт числа объектовПроизводящая функция]]
693
правки

Навигация