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

Для примера рассмотрим три объекта, обозначенные x₁, x₂, x₃. Образуем произведение

(1+x₁t)(1+ x₂t)(1+x₃t).

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

1+(x₁+x₂+x₃)t+(x₁x₂+x₁x₃+x₂x₃)t²+x₁x₂x₃t³,

или

1+а₁t+а₂t²+а₃t³,

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

(1+t)³=

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

(1+x₁t)(1+ x₂t)×....×(1+x_nt)=

=1+a₁(x₁,..., x_n)t+ a₂(x₁,..., x_n)t²+...+ a_n(x₁,..., x_n)tⁿ

и

(1+t)ⁿ==;

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

В произведении (1+x₁t)(1+ x₂t)×....×(1+x_nt) каждый множитель является биномом, который благодаря наличию в нем слагаемых 1 и x_i указывает на возможность наличия или отсутствия в каждом из сочетаний элемента x_i. Это произведение порождает сочетания, так как коэффициент при t^m в нем получается выбором “1” в n-m из n двучленных множителей и в m оставшихся после такого выбора множителях - членов вида x_it всеми возможными путями. Эти коэффициенты по самому их определению являются m-сочетаниями. Каждый элемент в любом сочетании может появляться не более одного раза, ибо любой множитель состоит только из двух слагаемых.

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

1+xt+xt⁴+ … +xt^2k.

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

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

(1+t+t²+...)ⁿ

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

(1-t)^-n = ==.

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

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

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