Изменения

Обычные [[Производящая функция {{Определение| Производящие функции ]] хранили одну последовательность чисел. Для задач, которые требуют больше информации применяются definition='''проивзодящие Производящие функции нескольких переменных''' (англ. ''multivariable generating function''){{---}} обычные [[Производящая функция | производящие функции]], зависящие более, чем от одной переменной. Для их применения нужно добавить переменные для образования последовательностей. Такие последовательности удобно задавать Очень часто применяются функции от двух переменных (далее они и будут рассматриваться), которые в виде треугольникаобщем случае принимают вид: <tex>G(x, y) = \sum\limits_{n, k \geqslant 0} g_{n, k} x^n y^k</tex>. }} Рассмотрим несколько примеров :

{{Определение|definition='''Треугольник Паскаля''' (англ. ''Pascal's triangle'') {{---}} бесконечная таблица биномиальных коэффициентов<ref>[[Filehttps:Pascal_triangle//ru.png|thumb|400px|right| Рисwikipedia.1]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 Биномиальные коэффициенты]</ref>, имеющая треугольную форму. В этом треугольнике на вершине и по бокам стоят единицы. Каждое число равно сумме двух расположенных над ним чисел.}}

Треугольник Паскаля изображен на рис[[File:Pascal_triangle.png|thumb|350px|right|Рис.<tex>1 . Элементы треугольника перечисляют пути, идущие из его вершины в соответствующую клетку. Пути имеют вид ломаных, составленных из векторов единичной длины двух видов : идущих вправо-вниз и идущих влево-вниз.</tex>]]

Числа, стоящие в треугольнике - биномиальные коэффициенты <tex> 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>вниз.

<tex>\sum\limits_{n,k = 0}^{\infty} c_{n,k} x^k y^n = \sum\limits_{n,k = 0}^{\infty} \begin{pmatrix} n \\ k \end{pmatrix} x^k y^n = \sum\limits_{n = 0}^{\infty}(\sum\limits_{k = 0}^{n} \begin{pmatrix} n \\ k \end{pmatrix} x^k) y^n = \sum\limits_{n = 0}^{\infty} (1 + x)^n y^n = \frac{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 = \fracdfrac{1}{1 -x - y}</tex>

Также существует еще один способ: сопоставить треугольнику Паскаля '''экспоненциальную проивзодящую производящую функцию'''. Экспоненциальная производящая функция отличается от обычной тем, что в качестве коэффициентов степенного ряда берутся не элементы последовательности <tex>a_n</tex>, а числа <tex>\fracdfrac{a_n}{n!}</tex>.

определяемую последовательностью <tex>\{ \alpha_n \}</tex>. Если в последовательности <tex>\{ \alpha_n \}</tex> отсутствуют нулевые элементы, то такое сопоставление взаимно однозначно. До сих пор мы пользовались обычными производящими функциями - , отвечающими последовательности <tex>\{ \alpha_n \} \equiv 1</tex>. В зависимости от преследуемых целей целей могут принести и другие последовательности . Чаще всего используется последовательность  {{Определение |definition='''Производящие экспоненциальные функции''' (англ. ''exponential generating function'') {{---}} функции, соответствующие последовательности <tex>\{ \alpha_n \} = \fracdfrac{1}{n!}</tex>. Соответсвующие ей производящие функции называются '''экспоненциальными'''(англ. ''exponential generating function'').}}

{{Определение |definition=Экспоненциальные производящие функции для целочисленных последовательностей называют '''функциями Гурвица''' (англ. Чем отличаются экспоненциальные производящие функции от обычных? Посмотрим на поведение экспоненциальных производящих функций при выполнении операции над ними''Hurwitz function''). Сумма ведет себя обычным образом:}}

Коэффициенты <tex>\fracbigg(\dfrac{a_0}{0!} + \dfrac{c_na_1}{n1!}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>c_n = \begindfrac{pmatrix} n \\ 0 \end{pmatrix} a_0 b_n + \begin{pmatrix} n \\ 1 \end{pmatrixc_n} a_1 b_{n - 1} + \dots + \begin{pmatrix} n \\ n \end{pmatrix!} a_0 b_0</tex>произведения вычисляются по формуле

<tex>\int bigg(\fracdfrac{a_0}{0!} + \fracdfrac{a_1}{1!}s + \fracdfrac{a_2}{2!}s^2 + \dots ldots \bigg) = \frac^{a_0'}{1!}s + = \fracdfrac{a_1}{20!}s^2 + \fracdfrac{a_2}{31!}s^3 + \fracdfrac{a_3}{42!}s^4 2 + \dots ldots </tex>

Обычная производящая функция <tex>A\displaystyle\int \bigg(s) = \dfrac{a_0 }{0!} + a_1s \dfrac{a_1}{1!}s + a_2s\dfrac{a_2}{2!}s^2 + \dots</tex> выражается через экспоненциальную <tex>ldots \mathcal{A} (tbigg) = \fracdfrac{a_0}{01!} s + \fracdfrac{a_1}{12!}t s^2 + \fracdfrac{a_2}{23!}s^3 + \dfrac{a_3}{4!}ts^2 4 + \dots ldots </tex> по формуле

Обычная производящая функция <tex>A(s) = a_0 + a_1s + a_2s^2 + \ldots</tex> выражается через экспоненциальную <tex>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>A(x^n) = ((x + 1)^{n+1} - x^{n+1}) / (n+1) = x^n + \ldots</tex>, где многоточие обозначает слагаемые, степени которых меньше <tex>n</tex>. Последняя формула показывает также, что преобразование <tex>A</tex> переводит пространство многочленов степени не выше <tex>n</tex> в себя, а значит, является линейным оператором в этом пространстве. Этот оператор обратим. Действительно, любой многочлен степени не выше <tex>n-1</tex> может быть получен в результате усреднения многочлена такой же степени, и, используя последнюю формулу, мы заключаем, что и любой многочлен степени не выше <tex>n</tex> является результатом усреднения некоторого многочлена степени не выше <tex>n</tex>. Отметим, что при усреднении степень многочлена сохраняется. {{Определение |definition='''Многочленом Бернулли''' (англ. ''Bernoulli polynomial'') степени <tex>n</tex> называется многочлен <tex>B_n(x)</tex>, результатом усреднения которого служит моном <tex>x^n</tex>, т.е. <tex>B_n(x) = A^{-1}(x^n)</tex>.}} Первые многочлены Бернулли нетрудно сосчитать: <tex>B_0(x) = 1</tex> <tex>B_1(x) = x - \dfrac{1}{2}</tex> <tex>B_2(x) = x^2 -x + \dfrac{1}{6}</tex> <tex>B_3(x) = x^3 - \dfrac{3}{2}x^2 + \dfrac{1}{2}x</tex> <tex>B_4(x) = x^4 - 2x^3 + x^2 - \dfrac{1}{30}</tex> <tex>B_5(x) = x^5 - \dfrac{5}{2}x^4 + \dfrac{5}{3}x^3 - \dfrac{1}{6}x</tex> <tex>B_6(x) = x^6 - 3x^5 + \dfrac{5}{2}x^4 - \dfrac{1}{2}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 - 1}e^{sx}</tex>.| proof = Для доказательства теоремы достаточно применить операцию усреднения к левой и правой частям равенства. С одной стороны, мы имеем:

<tex>\sum\limits_{nС другой стороны, m = 0}^{\infty} \frac{1}{(n + m)!} \begin{pmatrix} n + m \\ m \end{pmatrix} x^n y^m = \sum\limits_{n = 0}^{\infty} \frac{(x + y)^n}{n!} = e^{x + y}</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>,

[[File:Triangle_D_2и теорема доказана.png|thumb|500px|right|Рис.3 Представление треугольника Дика]]}}

Треугольник Дика перечисляет пути в положительном квадранте плоскости, выходящие из начала координат и составленные из векторов Определим теперь ''числа Бернулли''<texref>(1, 1)<[https:/tex> и <tex>(1, -1)</tex> (рисru.3)wikipedia. Мы можем увидеть, что элементы <tex>d_{ij}<org/tex> треугольника Дика отличны от нуля в том и только том случае, если <tex>i \ge j <wiki/tex> и <tex>i + j%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 числа Бернулли]</texref> четнокак значения многочленов Бернулли в нуле. Обозначим через <tex>D(x, y)</tex> производящую функцию Дика двух пременныхВот начало последовательности чисел Бернулли:

<tex>D(x1, y) = -\sumdfrac{1}{2}, 0, \dfrac{1}{6}, -\dfrac{1}{30}, \limits_dfrac{1}{i42},j =0, -\dfrac{1}{30}, \dfrac{5}^{66}, 0, -\inftydfrac{691} d_{ij2730} x^i y^j, 0, \ldots </tex>

Правило построения треугольника Дика подсказывает Доказанная теорема позволяет нам уравнение на эту легко выписать экспоненциальную производящую функциюдля чисел Бернулли. Для этого достаточно подставить в экспоненциальную производящую функцию для многочленов Бернулли значение <tex>x = 0</tex>:

<tex>xyD(x, y) + (D(x,y) - D(x,\displaystyle\sum\limits_{n=0))} B_n\fracdfrac{xs^n}{yn!} = D(x, y) \dfrac{s}{e^s - 1}</tex>.

Действительно, коэффициент при любом мономе <tex>x^iy^j</tex> , отличном от единичного, представляет собой сумму коэффициентов при мономах <tex>x^{i-1}y^{i-1}</tex> и <tex>x^{i-1}y^{j+1}</tex> ==См. Функция <tex>D(x, 0) также== \frac{1 - \sqrt{1 - 4x^2}}{2x^2}</tex> нам известна, и ряд <tex>D(x, y)</tex> находится решением линейного уравнения, *[[Производящая функция]]

<tex>D(x, y) = \frac{1 - \sqrt{1 - 4x^2} - 2xy}{2x(xy^2 + x - y)}=Примечания==<references/tex>

* ''ЛандоС. К.'', Лекции о производящих функциях. {{---}} 3-е изд., испр. {{---}} М.: МЦНМО, 2007. {{---}} 57с. ISBN 978-5-94057-042-4

[[Категория: Комбинаторика]][[Категория: Подсчёт числа объектовПроизводящая функция]]