Теоретические основы принципа включений — исключений

Формулировки принципа включений-исключений. Доказательство принципа включений-исключений

Словесная формулировка.

Принцип включений-исключений выглядит следующим образом:

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

Формулировка в терминах множеств.

В математической форме приведённая выше словесная формулировка выглядит следующим образом:

Её можно записать более компактно, через сумму по подмножествам. Обозначим через множество, элементами которого являются. Тогда принцип включений-исключений принимает вид:

Эту формулу приписывают Муавру (Abraham de Moivre).

Формулировка с помощью диаграмм Венна.

Пусть на диаграмме отмечены три фигуры, и :

Рис. 1.

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

.

Аналогичным образом это обобщается и на объединение фигур.

Формулировка в терминах теории вероятностей.

Если Ai (i=1…n) — это события, P (Ai) — их вероятности, то вероятность их объединения (т.е. того, что произойдёт хотя бы одно из этих событий) равна:

Эту сумму также можно записать в виде суммы по подмножествам множества, элементами которого являются события Ai.

комбинаторный математический множество исключение Доказательство принципа включений-исключений.

Для доказательства удобно пользоваться математической формулировкой в терминах теории множеств:

где, напомним, — это множество, состоящее из Ai-ых.

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

Рассмотрим произвольный элемент x, содержащийся ровно в множествах Ai. Покажем, что он посчитается формулой ровно один раз.

Заметим, что:

• · в тех слагаемых, у которых size (C)=1, элемент x учтётся ровно k раз, со знаком плюс;
• · в тех слагаемых, у которых size (C)=2, элемент x учтётся (со знаком минус) ровно раз — потому что x посчитается только в тех слагаемых, которые соответствуют двум множествам из k множеств, содержащих x;
• · в тех слагаемых, у которых size (C)=3, элемент x учтётся ровно раз, со знаком плюс;
• · в тех слагаемых, у которых size (C)=k, элемент x учтётся ровно раз, со знаком (-1)k-1;
• · в тех слагаемых, у которых size (C)>k, элемент x учтётся ноль раз.

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

Проще всего посчитать эту сумму, сравнив её с разложением в бином Ньютона выражения (1-x)k:

Видно, что при x=1 выражение (1-x)k представляет собой не что иное, как 1-T. Следовательно, T=1-(1−1)k=1, что и требовалось доказать.

Принцип включений-исключений сложно хорошо понять без изучения примеров его применений.

Сначала мы рассмотрим три простые задачи «на бумажке», иллюстрирующие применение принципа, затем рассмотрим более практические задачи, которые трудно решить без использования принципа включений-исключений.

Особо следует отметить задачу «поиск числа путей», поскольку в ней демонстрируется, что принцип включений-исключений может иногда приводить к полиномиальным решениям, а не обязательно экспоненциальным.