§ 8. Применение производящей функции. Энумераторы и денумераторы сочетаний

Рассмотрим некоторое множество объектов этому множеству сопоставим последовательность так, что соответствует Образуем производящую функцию

Осуществим разложение (8.1):

Полагаем

Коэффициенты , дают перечисление неупорядоченных -выборок без повторения, или сочетаний без повторения из объектов по если заменить на Производящую функцию вида (8.1) назовем энумератором Положим в (8.1)

Тогда

Если положим теперь

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

Рассмотрим сначала, как используются некоторые денумераторы, а к энумераторам вернемся несколько позднее. Подставим в Получаем

Подставим теперь в

Складывая (8.7) и (8.8) и деля результат на 2, получаем

Вычитая, получаем

Подставим теперь денумератор (8.5) так:

В силу (8.5) имеем

Подставим (8.14) в (8.13):

Во второй сумме справа в (8.15) заменяем на й:

Заметим, что Сокращаем члены с соответствующими коэффициентами в (8.16):

Это тождество относительно дает

Найденное соотношение хорошо известно из треугольника Паскаля.

Запишем теперь (8.5) по-другому:

Разлагая согласно (8.14), получаем в левой и правой частях выражения

следующие коэффициенты при

Для удобства будем пользоваться обозначением

ввиду следующего свойства. По определению

Ничто не препятствует в этой формуле взять отрицательным не будет тогда числом сочетаний из и по ) и обозначить через величину

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

Осуществляя разложение и заменяя затем на имеем

т. е.

Таким образом, способом, отличным от § 3, мы опять получили число сочетаний с повторением (число неупорядоченных гвыборок с повторением).

Попытаемся подсчитать число неупорядоченных -выборок с повторением, в которых каждый объект встречается не менее одного раза. С этой целью рассмотрим такой денумератор:

Полагая и учитывая, что находим

Таким образом, число неупорядоченных -выборок с повторением, в которых каждый объект встречается не менее одного раза, равно

Пример. Даны два объекта Сколько всего существует четырехэлементных сочетаний из этих двух объектов, в которых каждый объект встречается не менее одного раза? Это число равно

Выписываем эти сочетания:

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

Если положим то

Таким образом, искомое число равно

Пример. Даны три объекта Каково число восьмиэлементных сочетаний с повторением из этих объектов по 8, в которых каждый объект встречается не менее двух раз? Имеем

Выпишем эти сочетания:

Подсчитаем число сочетаний из объектов по элементов с повторением, в которых каждый объект встречается четное число раз. Для этого рассмотрим денумератор

Таким образом,

Вообще при условии, что каждый объект встречается число раз, кратное следует использовать такой денумератор:

Итак,

Рассмотрим теперь условия более общего вида, чем те, что встречались до сих пор в этом параграфе.

Предположим, что объект встречается не менее раз, не менее раз, не менее раз. Тогда в качестве энумератора можно взять

а в качестве денумератора

Предположим, что объект встречается не более раз, не более раз, не более раз. Тогда в качестве энумератора можно взять

а в качестве денумератора

Пусть теперь количество появлений объекта одно из чисел

количество появлений объекта одно из чисел

количество появлений объекта одно из чисел

Тогда в качестве энумератора можно взять

а в качестве денумератора

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

Пример. Перечислить сочетания с повторением из 3 объектов по элементов при условии, что встречается не более одного раза, более двух, а один или два раза. Тогда энумератором служит

Для возможных значений имеем

Денумератор равен

Если обозначает число сочетаний с указанными ограничениями, то

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

Например, пусть таково, что выполняются следующие условия:

Тогда будет соответствовать пересечение

Член энумератора, соответствующий и удовлетворяющий условиям, будет

Еще один пример.

Предположим, что на наложено следующее условие: присутствие исключает присутствие никогда не встречаются вместе).

Пусть также дано условие:

присутствуют как так и тогда соответствующим множеством коэффициентов будет

для нахождения нужно взять дополнение указанного множества по отношению к множеству, дающему все неупорядоченные -выборки с повторением, образованные с по отношению к множеству

следовательно, множеством коэффициентов, соответствующим будет

Тогда энумератор есть

Рассмотрим вкратце еще один пример. Даны четыре объекта на которые наложены следующие условия:

если А встречается четное число раз, то В встречается нечетное число раз и наоборот;

Имеем

УПРАЖНЕНИЯ

(см. скан)