Изменения
sta
Обычные [[Производящая функция | Производящие функции ]] хранили одну последовательность чисел. Для задач, которые требуют больше информации применяются '''проивзодящие производящие функции нескольких переменных''' (англ. ''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|rightcenter| Рис.<tex>1</tex>]]
Треугольник Паскаля изображен на (рис.<tex>1 </tex>). Элементы треугольника перечисляют пути, идущие из его вершины в соответствующую клетку. Пути имеют вид ломаных, составленных из векторов единичной длины двух видов : идущих вправо-вниз и идущих влево-вниз.
{{Теорема|statement= Числа, стоящие в треугольнике - биномиальные коэффициенты <tex> c_{n,k} = \begin{pmatrix} n \\ k \end{pmatrix}</tex>.|proof= Числа, стоящие в треугольнике - биномиальные коэффициенты <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}\Big(\sum\limits_{k = 0}^{n} \begin{pmatrix} n \\ k \end{pmatrix} x^k\Big) y^n = \sum\limits_{n = 0}^{\infty} (1 + x)^n y^n = \dfrac{1}{1 - y - xy}</tex>
[[File:Pascal_triangle_3.png|thumb|600px|right|Рис.<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}2</tex>]]
<tex>\sum\limits_{n,m = 0}^{\infty} C_{n, m} x^n y^m = \sum\limits_{n,m = 0}^{\infty} \begin{pmatrix} n + m \\ m \end{pmatrix} x^n y^m = \sum\limits_{k = 0}^{\infty} \sum\limits_{n + m = k} \begin{pmatrix} n + m \\ n \end{pmatrix}
x^n y^m = \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 \} \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>. В зависимости от преследуемых целей целей могут принести и другие последовательности . Чаще всего используется последовательность <tex>\{ \alpha_n \} = \frac{1}{n!}</tex>. Соответсвующие ей производящие функции называются '''экспоненциальными'''(англ. ''exponential generating function'').
{{Определение |definition=Экспоненциальные производящие функции для целочисленных последовательностей называют '''функциями Гурвица'''(англ. ''Hurwitz function'').}} Чем отличаются экспоненциальные производящие функции от обычных? Посмотрим на поведение экспоненциальных производящих функций при выполнении операции над ними. Сумма ведет себя обычным образом: <tex>\sum\limits_{n = 0}^{\infty} \fracdfrac{a_n}{n!}s^n + \sum\limits_{n = 0}^{\infty} \fracdfrac{b+n}{n!}s^n = \sum\limits_{n = 0}^{\infty} \fracdfrac{(a_n + b_n)}{n!} s^n</tex>
а с произведением по-другому :
<tex>\bigg(\fracdfrac{a_0}{0!} + \fracdfrac{a_1}{1!}s + \fracdfrac{a_2}{2!}s^2 + \dotsldots\bigg)\bigg(\fracdfrac{b_0}{0!} + \fracdfrac{b_1}{1!}s + \fracdfrac{b_2}{2!}s^2 + \dotsldots\bigg) = \fracdfrac{a_0}{0!} \fracdfrac{b_0}{0!} + \bigg(\fracdfrac{a_0}{0!} \fracdfrac{b_1}{1!} + \fracdfrac{a_1}{1!} \fracdfrac{b_0}{0!}\bigg)s + \bigg(\fracdfrac{a_0}{0!} \fracdfrac{b_2}{2!} + \fracdfrac{a_1}{1!} \fracdfrac{b_1}{1!} + \fracdfrac{a_2}{2!} \fracdfrac{b_0}{0!}\bigg)s^2 + \dotsldots</tex>
Коэффициенты <tex>\fracdfrac{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} + \dots ldots + \begin{pmatrix} n \\ n \end{pmatrix} a_0 b_0</tex>
Еще одно существенное отличие экспоненциальных производящих функций от обычных наблюдается при взятии производных (и интегрировании). Дифференцирование или интегрирование экспоненциальной производящей функции приводит к сдвигу последовательности ее коэффициентов без изменения их велечины :
<tex>\bigg( \fracdfrac{a_0}{0!} + \fracdfrac{a_1}{1!}s + \fracdfrac{a_2}{2!}s^2 + \dots ldots \bigg)^{'} = \fracdfrac{a_1}{0!} + \fracdfrac{a_2}{1!}s + \fracdfrac{a_3}{2!}s^2 + \dots ldots </tex>
<tex>\int \bigg(\fracdfrac{a_0}{0!} + \fracdfrac{a_1}{1!}s + \fracdfrac{a_2}{2!}s^2 + \dots ldots \bigg) = \fracdfrac{a_0}{1!}s + \fracdfrac{a_1}{2!}s^2 + \fracdfrac{a_2}{3!}s^3 + \fracdfrac{a_3}{4!}s^4 + \dots ldots </tex>
Обычная производящая функция <tex>A(s) = a_0 + a_1s + a_2s^2 + \dotsldots</tex> выражается через экспоненциальную <tex>\mathcal{A} (t) = \fracdfrac{a_0}{0!} + \fracdfrac{a_1}{1!}t + \fracdfrac{a_2}{2!}t^2 + \dots ldots </tex> по формуле
<tex>A(s) = \int_{0}^{\infty} e^{-t} \mathcal{A}(st) dt</tex>
Теперь можно выписать экспоненциальную производящую функцию для треугольника Паскаля :
<tex>\sum\limits_{n, m = 0}^{\infty} \fracdfrac{1}{(n + m)!} \begin{pmatrix} n + m \\ m \end{pmatrix} x^n y^m = \sum\limits_{n = 0}^{\infty} \fracdfrac{(x + y)^n}{n!} = e^{x + y}</tex>
==Треугольник Дика==
[[File:Triangle_D_2.png|thumb|500px|right|Рис.<tex>3 </tex> Представление треугольника Дика]]
Треугольник Дика перечисляет пути в положительном квадранте плоскости, выходящие из начала координат и составленные из векторов <tex>(1, 1)</tex> и <tex>(1, -1)</tex> (рис.<tex>3</tex>). Мы можем увидеть, что элементы <tex>d_{ij}</tex> треугольника Дика отличны от нуля в том и только том случае, если <tex>i \ge geqslant j </tex> и <tex>i + j</tex> четно. Обозначим через <tex>D(x, y)</tex> производящую функцию Дика двух пременных
<tex>D(x, y) = \sum\limits_{i,j =0}^{\infty} d_{ij} x^i y^j</tex>
Правило построения треугольника Дика подсказывает нам уравнение на эту производящую функцию
<tex>xyD(x, y) + (D(x,y) - D(x,0))\fracdfrac{x}{y} = D(x, y) - 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) = \dfrac{1 - \sqrt{1 - 4x^2}}{2x^2}</tex> нам известна, и ряд <tex>D(x, y)</tex> находится решением линейного уравнения,
==Источники информации==
* ''ЛандоС. К.'' ''Лекции о производящих функциях'' {{---}} МЦНМО, 2007 - С. 57
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]
[[Категория: Подсчёт числа объектов]]
