Производящие функции для перестановок.

В случае коммутативных алгебраических операций произведения х₁х₂ и х₂х₁ одинаковы. Поэтому производящую функцию, описывающую перестановки, невозможно построить так, как это было сделано для сочетаний. В случае n различных элементов из соотношения p(n,m)=”число m-перестановок” вытекает, что (1+t)ⁿ = , т. е. в разложении выражения (1+t)ⁿ число p(n,m) является коэффициентом при . Этот факт указывает пути обобщения.

Если какой-либо элемент может появляться 0,1,…,k раз или если существует k элементов данного вида, то множитель 1+t в левой части равенства заменяется множителем 1+t++…+. Это объясняется тем, что число перестановок из n элементов, p из которых одного вида, q другого и т. д., равно

.

Это число оказывается коэффициентом при в произведении

  , n=p+q+…,

что в точности соответствует необходимым требованиям.

Определение и простейшие свойства производящих функций.1

Определение. Обычной производящей функцией для последовательности a₀,a₁,… называется формальная сумма

A(t)=a₀+a₁t+a₂t²+ … a_ntⁿ+… . (1)

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

Е(t)=a₀+a₁t+a₂t²/2!+ … a_ntⁿ/n!+… . (2)

В связи с этими определениями необходимо сделать несколько замечаний. Во-первых, элементы последовательности a₀,a₁,…, как видно, из самих обозначений, упорядочены, но не обязательно должны быть различны. Во-вторых, переменная t производящей функции никак не определена.

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

Алгебра степенных рядов A(t), определяющих производящие функции, известна под именем алгебры Коши, а алгебра степенных рядов E(t), определяющих экспоненциальные производящие функции, известна как символическое исчисление Блиссара. В статистике функция E(t) фигурирует как производящая функция моментов; E(t) используется также в теории чисел.

В комбинаторике неизбежно возникают производящие функции, отличные от А(t) или E(t), например, сумма вида

G(t)= a₀f₀(t)+a₁f₁(t)+a₂f₂(t)+ … a_nf_n(t)+…, (*)

для которой единственным требованием является линейная независимость функций f₀(t), f₁(t),…(для того чтобы сделать выражение однозначным). A(t) и E(t) являются частными случаями этого выражения.

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

А(t)=

Этот факт, по-видимому, более известен для случая экспоненциального ядра е^-tk, т. е. для преобразования Лапласа

А(t)=

Выражение, включающее в себя как частные случаи оба приведенные выше интеграла и степенные ряды, представляет собой интеграл Стильтьеса

А(t)=,

в котором t – параметр. Чтобы получить сумму (1), в качестве функции F(t,k) выбираем ступенчатую функцию. Эта функция имеет скачки при к=0,1,2,…; скачок в точке k равен t^k.

Некоторые простейшие производящие функции.

ak	A(t)	E(t)
ak	(1-at)-1	Exp at
k	t(1-t)	t exp t
k(k-1)	2t2(1-t)-3	t2 exp t
k2	t(t+1)(1-t)-3	t(t+1) exp t
c	(1+t)n	-
n(n-1)…(n-k+1)	-	(1+t)n

Упражнение. Докажите справедливость приведенных формул.

Элементарные соотношения между обычными производящими функциями.

Обозначим через A(t), B(t), C(t) производящие функции, соответствующие последовательностям (а_к), (b_к), (c_к), тогда в качестве непосредственного следствия из самого определения последовательности (а) получаем две пары соотношений; в каждой паре выполнение одного из соотношений влечет за собой выполнение второго

Сумма а_к=b_к+c_к

A(t)=B(t)+C(t)

Произведение а_к=b_кc₀+b_к-1c₁+…+b₁c_к-1+b₀c_к

A(t)=B(t)C(t)

Последовательность (а_к) называется сверткой (b_к) и (c_к), если A(t)=B(t)C(t). Сумма и произведение обладают свойствами коммутативности и ассоциативности.

Для экспоненциальных производящих функций соответствующие соотношения определяются следующим образом:

Пусть E(t), F(t), G(t) экспоненциальные производящие функции, соответствующие последовательностям (e_к), (f_к), (g_к), тогда

Сумма e_к=f_к+g_к

E(t)=F(t)+G(t)

Произведение e_к=f_кg₀+f_к-1g₁+…+f₁g_к-1+f₀g_к

E(t)=F(t)G(t)