Главная теорема комбинаторики (Теорема о включениях и исключениях)
   Пример. На предприятии работает 67 человек. Из них 48 знают английский, 35 - немецкий и 27 - оба языка. Сколько человек не знают ни английского, ни немецкого?
   Результат можно получить следующим образом. Построим диаграмму, на которой изобразим прямоугольник, соответствующий общему числу работающих (67) и две пересекающиеся области А и В по 48 и 35 человек ( знающих английский и немецкий языки). На диаграмме общая часть этих двух областей соответствует 27 - количеству работащих, которые знают оба языка. Требуется найти область прямоугольника, не входящую ни в область А, ни в область В.
 





     Очевидно, что N = 67 - 48 - 35 + 27 = 11.
Главная теорема комбинаторики (Теорема о включениях и исключениях)
   Пусть имеется множество из N объектов произвольной природы. На этом множестве пусть задано n свойств. Каждый объект может обладать либо не обладать некоторыми из этих свойств. Сами свойства обозначим:                                          . Будем обозначать          - количество объектов точно обладающих свойством     , и может быть какими-то другими, а                   - число объектов не обладающих ни свойством       , ни свойством     . Тогда число объектов, не обладающих ни одним из перечисленных свойств:

  
                                                                                                                    (6)



    Продолжение примера. Пусть теперь 20 человек знают французский, 12 - английский и французский, 11 - английский и немецкий и 5 - все три языка.
    Тогда в соответствии с теоремой количество человек, не знающих ни одного из трех перечисленных языков (но может быть знающих китайский язык), равно N= 67 - 48 - 35 - 20 + 27 + 12 + 11 - 5 = 9.
Решето Эратосфена
    Выпишем все числа от 1 до N. Сколько чисел делится на k? Очевидно, [N/k], где [х] обозначает целую часть числа х. Тогда, легко подсчитать количество чисел, не делящихся в данном диапазоне на 
    Пример. Сколько чисел от 1до 100 не делятся на 5 и 7?
   Воспользуемся теоремой о включениях и исключениях. Под первым свойством чисел будем понимать делимость на 5, под вторым - делимость на 7. На 5 делятся 20 чисел. На 7 делятся 14 чисел. На 35 делятся 2 числа. Следовательно, не делятся на 5 и 7: 100 - 20 - 14 + 2 = 68 чисел.
    Упражнения
   1. В механической мастерской работают 12 человек, из них 6 человек имеют диплом слесаря, 4 - диплом оператора станков с ЧПУ, 7 человек - диплом фрезеровщика, по 3 человека владеют двумя из перечисленных специальностей и 2 человека - всеми тремя. Начальство решает уволить работников, не имеющих дипломов хотя бы по одной из этих специальностей. Имеется ли такая возможность?
    2. 3 танкиста, 2 артиллериста, 1 интендант и 4 пехотинца решили сфотографироваться.
Сколько разных фотографий может получиться, если все они располагаются в ряд и все представители одной группы войск находятся рядом?
    3. Найти количество чисел, не делящихся на 3, 5, 7, в диапазоне от 200 до 500?

Закрыть