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

В случае коммутативных алгебраических операций произведения х₁х₂ и х₂х₁ одинаковы. Поэтому производящую функцию, описывающую перестановки, невозможно построить так, как это было сделано для сочетаний. В случае 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)
a^k	(1-at)^-1	Exp at
k	t(1-t)	t exp t
k(k-1)	2t^2(1-t)^-3	t^2 exp t
k^2	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)

Дата добавления: 2014-01-06