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

Для примера рассмотрим три объекта, обозначенные x1, x2, x3. Образуем произведение

(1+x1t)(1+ x2t)(1+x3t).

Перемножив и разложив это произведение по степеням t, получим

1+(x1+x2+x3)t+(x1x2+x1x3+x2x3)t2+x1x2x3t3,

или

1+а1t+а2t23t3,

где а1, а2, а3 – элементарные симметрические функции трех переменных x1, x2, x3. Эти симметрические функции определяются вышеприведенным выражением. Можно заметить, что число слагаемых каждого коэффициента аm (m=1,2,3) равно числу сочетаний из трех элементов по k. Следовательно, число таких сочетаний получается приравниванием каждого xi единице, т. е.

(1+t)3=

Для случая n различных объектов, обозначенных x1, . . . , xn ясно, что

(1+x1t)(1+ x2t)× . . . .×(1+xnt)=

=1+a1(x1,. . ., xn)t+ a2(x1,. . ., xn)t2+. . .+ an(x1,. . ., xn)tn

и

(1+t)n==;

поэтому выражение (1+t)n называют перечисляющей функциейсочетаний из n различных объектов. Этот результат можно также обосновать следующими комбинаторными рассуждениями:

В произведении (1+x1t)(1+ x2t)× . . . .×(1+xnt) каждый множитель является биномом, который благодаря наличию в нем слагаемых 1 и xi указывает на возможность наличия или отсутствия в каждом из сочетаний элемента xi. Это произведение порождает сочетания, так как коэффициент при tm в нем получается выбором “1” в n-m из n двучленных множителей и в m оставшихся после такого выбора множителях - членов вида xit всеми возможными путями. Эти коэффициенты по самому их определению являются m-сочетаниями. Каждый элемент в любом сочетании может появляться не более одного раза, ибо любой множитель состоит только из двух слагаемых.

Обобщая эти комбинаторные рассуждения, для случая, когда прежние множители вида 1+xit заменяются множителями вида 1+xt+xt2+ … +xtj, построим производящую функцию для сочетаний, в которых элементы xi могут содержаться 0,1,2,…,j раз. Более того, множители производящей функции можно совершенно независимо друг от друга приспосабливать к любым требованиям задачи. Так, например, если xk должно всегда входить четное число раз, но не более чем 2k раз, то k-й множитель следует выбирать в виде

1+xt+xt4+ … +xt2k .

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

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

(1+t+t2+. . .)n

или, что же самое

(1-t)-n = ==.

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

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