§ 12. Формула включения и исключения

Пусть А — конечное множество и Будем обозначать через дополнение по отношению к А, а через — число элементов в А. Тогда

Если , то

В самом деле

и

откуда

и

Покажем, что формула (12.2) обобщается на случай подмножеств

Действуем по Индукции. Имеем

Предположим, что (12.7) выполняется для случая подмножеств :

Рассмотрим следующие подмножества множества

Применяя (12.9) с имеем

Подставляя (12.10) и (12.9) в (12.8), получаем (12.7). Таким образом, с учетом (12.2) формула (12.7) доказана по индукции. Эту формулу называют формулой включения и исключения. Часто представляют ее в таком виде:

Формулы (12.7) и (12.11) играют основную роль в перечислении подмножеств, обладающих заданными свойствами. Посмотрим на эти формулы с другой точки зрения.

Пусть элементы обладают свойством Тогда мы скажем, что подмножество обладает свойством Таким образом, если элементы А могут обладать различными свойствами, то число элементов А, обладающих указанными свойствами и не обладающих остальными, дается формулой (12.11).

Общий метод «просеивания» или «пропускания через решето». Решето Сильва — Сильвестра. Формула (12.11) описывает последовательный процесс пересчета, называемый решетом Сильва — Сильвестра. Рассмотрим предварительно пример. Пример. Рассмотрим множество

и следующие свойства:

Подсчитаем число элементов А, обладающих свойством: не не , т. е. Обозначим подмножества, соответствующие свойствам через Тогда

«Просеиваем» сначала А через Затем просеиваем через Просеиваем через Итак,

Формула (12.11) не позволяет, однако, перечислить элементы искомого множества. Находим его, выписывая последовательно:

Разумеется, для множества с небольшим числом элементов проще выписать искомое подмножество, однако это трудно сделать при большой мощности множества.

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

где суммирование производится по всем неупорядоченным -выборкам и

Обозначим через число элементов А, удовлетворяющих в точности свойствам, не уточняя, каким именно, или, что то же самое, не удовлетворяющих в точности свойствам. В силу (12.11) имеем

В частности, если е. никакое свойство не выполняется, то

Пример. Рассмотрим предыдущий пример (см. (12.13)):

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

одно число не удовлетворяет никакому из указанных свойств:

пять чисел А удовлетворяют в точности одному свойству: ;

пять чисел А удовлетворяют в точности двум свойствам: ; ни одно из чисел А не удовлетворяет в точности трем свойствам.

Общая формула включения и исключения. Пусть А — конечное множество. Каждому элементу припишем вес Пусть 5 — множество из свойств которым могут удовлетворять элементы А. Обозначим через

сумму весов элементов А, удовлетворяющих свойствам полагаем если ни один из элементов А не удовлетворяет ни одному из указанных свойств.

Пусть

где суммирование производится по всем -элементным подмножествам множества сумма весов всех элементов А. Далее, пусть -сумма весов элементов А, удовлетворяющих в точности свойствам из 5:

Если вес каждого элемента из А равен 1, то

и

Формула (12.24) сводится к (12.19).

Докажем (12.24), следуя Райзеру [35]. Пусть элемент с весом обладает в точности свойствами из При не входит в правую часть (12.24). При вклад а» в правую часть (12.24) равен а при равен

Легко видеть, что

Подставляя (12.29) в (12.28), получаем

или

Но в силу (8.8) выражение в скобках равно нулю, т. е. при вклад в правую часть (12.24) равен нулю. Таким образом, член справа в (12.24) есть сумма весов элементов из А, удовлетворяющих в точности свойствам из При

что обобщает (12.20).

Пример. Пусть элементы множества удовлетворяют следующим свойствам:

Этим свойствам соответствуют подмножества:

Зададим веса элементов таблицей:

Для вычисления по формуле (12.24) требуются следующие величины:

(см. скан)

(см. скан)

Сумма весов элементов, не удовлетворяющих ни одному из свойств, равна

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

Сумма весов элементов, удовлетворяющих одному и только одному свойству, равна

Такими элементами являются:

Сумма их весов

Сумма весов элементов, удовлетворяющих в точности двум свойствам, равна Такими элементами являются:

Сумма их весов

Сумма весов элементов, удовлетворяющих в точности трем свойствам, равна

Такими элементами являются:

Сумма их весов

Сумма весов элементов, удовлетворяющих в точности четырем свойствам, равна

Таким элементом является Итак, множество А разбивается на подмножества, обладающие

Символическая запись формулы включения и исключения. Риордан [36] связал с принципом включения и исключения некоторые символические операции. Чтобы изложить это, нам потребуются результаты § 10 (см. (10.62) — (10.88)).

Пусть подмножества обладают свойствами соответственно. Полагаем

Деля (12.20) на записываем

Точно так же

Заметим, что величины можно рассматривать как вероятности того, что элемент обладает в точности свойствами. Перепишем формулу (10.88):

Очевидно,

Итак, числа биномиальные моменты распределения с вероятностями . В силу (10.67)

Пусть производящая функция для

Выписываем факториальные моменты для (согласно

и производящую функцию для них

В силу (10.80)

Введем производящую функцию для биномиальных моментов

Тогда в силу (10.80)

Теперь найдем производящую функцию для Имеем

и

Таким образом, производящая функция для представляется в виде

Пример. Вновь рассмотрим пример (см. (12.13)). В силу (12.21)

Получаем коэффициенты полинома уже найденные в (12.21).

УПРАЖНЕНИЯ

(см. скан)