Метод включений и исключений

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

Пусть дано n- множество некоторых элементов и к-множество свойств , которыми элементы могут как обладать, так и не обладать. выделим какую-либо r-выборку свойств . Число элементов обладающих всеми r выбранными свойствами, обозначим через . Отсутствие у элемента какого-либо свойства будем обозначать .

Найдем число элементов, не обладающих набором определенных свойств, начав с простых случаев:

1. Пусть имеется одно свойство , тогда .

2. Имеется конечное число свойств , несовместимых друг с другом. Тогда .

3. Элементы обладают комбинациями различных свойств. Тогда справедлива теорема.

Теорема3. Если даны n- множество элементов и к-множество свойств , , совместимых между собой, тогда

(20)

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

(21)

Пример. В комнате несколько человек, знающих хотя бы один из трех языков. Шестеро знают английский, шестеро – немецкий, семеро – французский. Четверо знают английский и немецкий, трое – немецкий и французский, двое – французский и английский. Один человек знает все три языка. Сколько человек в комнате. сколько из них знают только английский язык.

Решение. Пусть свойство - знать английский язык; и - свойства, характеризующие знание немецкого и французского языков. По условию задачи общее число людей составляют все, знающие хотя бы один язык; не знающих хотя один язык в задаче нет. Тогда