Другие виды производящих функций

Последовательности с двумя индексами

Производящие функции от двух переменных отвечают двух индексным последовательностям. Также последовательности удобно записывать в виде треугольника (соответствующего положительному квадранту целочисленной решётки).

Треугольник Паскаля.

Треугольник Паскаля изображён ниже.

Элементы этого треугольника перечисляют пути, идущие из его вершины в соответствующую клетку. Пути имеют вид ломанных, состоящих из векторов единичной длины двух видов: идущих влево — вниз и идущих вправо — вниз.

Числа, стоящие в треугольнике Паскаля — биномиальные коэффициенты.

Докажем данную формулу при помощи индукции по Предположи, что числа в ой строчке треугольника совпадают с коэффициентами разложения многочлена, Числа различных путей, ведущих в точку равно сумме числа путей, ведущих в точку и числа путей, ведущих в точку. Поэтому число совпадает с коэффициентом при в многочлене.

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

Второй способ соответствует нумерации элементов треугольника числом отрезков каждого типа, на путях ведущих в соответствующую точку. Для этой нумерации.

И производящая функция имеет вид.

В данном случае производящая функция оказалась симметричной по переменным .