Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

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

Для примера рассмотрим три объекта, обозначенные 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+x t+x t²+ … +x t^j, построим производящую функцию для сочетаний, в которых элементы x_i могут содержаться 0,1,2,…,j раз. Более того, множители производящей функции можно совершенно независимо друг от друга приспосабливать к любым требованиям задачи. Так, например, если x_k должно всегда входить четное число раз, но не более чем 2k раз, то k-й множитель следует выбирать в виде

1+x t+x t⁴+ … +x t^2k.

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

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

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

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

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

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

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