Принцип включения-исключения

Этот метод (просеивания) известен еще с работ Бернулли. Решето Эратосфена – разновидность принципа включения-исключения.

Рассмотрим некоторое множество A₁ как универсальное множество. Это множество обладает рядом свойств:

, которое обладает свойством

(Дополнение не обладает свойством , а обладает свойством )

(1)

Наряду с рассмотрим подмножество , которое обладает свойством

Требуется найти число подмножеств не обладающих ни ни , то есть их объединения

Если взять все элементы множества A и удалить все не обладающие ни ни , то получим нужное нам свойство включения-исключения:

Найдем число элементов полученного множества (2) с помощью диаграмм Эйлера-Венна

= -

Поставим (3) во (2):

=

Формулу (4) можно распространить на любое число аналогично. Свойств, то есть можно считать, что:

, , причем, все элементы = обладают свойством , а не обладают таким свойством, так как не существует взаимо-однозначных соответствий между элементами множества и подмножества, то есть они близки или похожи.

Раздел математики Функторы и категории.

Для уравнения (4) характерно следующее выражение:

1)Множество не обладает свойством (

2) обладает свойством ( хотя бы одним

3) Здесь в (5) сумму ров. осущ. По всем сочетаниям без повторения, a представляет собой число элементов, обладающих по крайней мере 2-мя свойствами

4) По крайней мере 3-мя свойствами

5) Подмножество обладает всеми свойствами

Предположим для доказательства справедливости следующее соотношение:

(6)

Считаем, что все элементы обладают , и каждому члену выражения (6) добавим , тогда получим следующее выражение:

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

?

В выражение (8) подставим (6) и (7) и получим после объединения и преобразования выражение (5).

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

Пример: часто ставится задача найти число элементов A, обладающих k-заданным свойством.

, … и не обладающее n-k свойствами , …

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

Пример: подмножество A=

Свойства:

: ,

: ,

: 8

Найти , т.е.

= - -( )+ =

(0;6)

=6-2-

Формула (9) позволяет определить число элементов Aс заданными свойствами.

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

Это число обозначает W(k). Для этого введем сведущее обозначение :

Т.е. здесь записано число элементов, обладающих k-

, …

Произведем суммирование по всем k-сочетаниям без повторений из заданных n-подмножеств, тогда:

W(k)

W(0)=

Исходя из (9) можно доказать, что W(k) есть число элементов, обладающих в точности k-свойствами и равными

Если мы хотим найти число элементов, не обладающих некоторыми свойствами, мы можем прибавить r=0, при этом получим

Пример:

Задача о беспорядках (как пример метода включений/исключений)

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

Q – множество ячеек, которые нужно поместить в A. Найти, каким количеством способов в множество Q по одному элементов в каждую ячейку, при чем ни один элемент не должен попадать в ячейку то есть в соседнюю ячейку.

Необходимо найти общее число беспорядков. Пусть , где i=1,…2-n!

Если есть беспорядок, то он обладает свойствами P_0. Если в перестановке элемент попадает в ячейку , то обладает свойством :

- множество всех перестановок, в которых не переходит в , а объединение - множество всех беспорядков.

W(n) – число перестановок, имеющих…

Для нахождения

совпадений, тогда Есть число совпадений с фиксированным беспорядком.

Если (4) подставить в (3) то получится

при достаточно большом r