Дипломная работа

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

Изучая свойства сочетаний (на таблице) было показано, что числа сочетаний совпадают с биномиальными коэффициентами, т.е.

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

Пример.



а). t=1
б). t=-1

Рассмотрим а) + б).

Пусть i – четное. Тогда

…………………………….

Пусть i – нечетное.

…………………………….

Тогда а) + б) даст

Вычтем из а) б). Тогда:

а) Пусть i – четное, тогда




……………
……………………………….

б). Пусть i – нечетное, тогда

…………………
………………………………

перемножим и суммируем члены при t.

…………………………………………….

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

2.4.7 Производящие функции при одинаковых элементах в комбинациях сочетания

n штук

o o o o ……… o

(1+t) (1+t) (1+t) (1+t) (1+t)

Если элементы не различны

o o o ….……. o
(1+x1t) (1+x2t) (1+x3t) (1+xnt)

идентифицирующие элементы

Тогда для 3-х элементов с учетом идентифицирующих элементов




1 + 3 + 3 + 1

! Все , , - симметричные функции переменных , , .

! Число слагаемых каждого коэффициента равно числу сочетаний:

Это справедливо для случая из n элементов.

если , то получаем

! Коэффициенты по своей сути являются r-сочетаниями. При этом каждый элемент в сочетании появится не более 1 раза.

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

если входит хотя бы один раз в сочетание (но не более i раз)

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

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









число предметов в выборке

число сортов предметов


r - число предметов, которые выбираем,
k – число типов предметов

Введем еще одно условие для задачи из примера 1:

В каждое сочетание непременно должен входить по крайней мере один элемент каждого вида.
В этом случае будем иметь:

(сменим индексацию )

n – число сортов предметов, которые порождают комбинации
j – число предметов в комбинации (число предметов в выборке)

Пусть имеем 3 класса предметов. Сколько из них моно составить комбинаций, содержащих 5 предметов? Условие: в комбинацию входят предметы каждого класса. Классы предметов – a, b, c.

1). aaabc 2). abbbc 3). abccc 4). aabbc 5). aabcc 6). abbcc