Если X1,X2,…,Xn некоторые подмножества множества X, причем в общем случае , то справедлива формула (1.47), которая в комбинаторике называется Формулой включений и исключений:
|X1È…ÈXn|=(|X1|+…+|Xn|)-(|X1ÇX2|+|X1ÇX3|+…+|Xn-1ÇXn|)+
+(|X1ÇX2ÇX3|+…+|Xn-2ÇXn-1ÇXn|)-…+(-1)n+1|X1Ç…ÇXn|. (2.14)
Следствием этой формулы является равенство:
|X\(X1È…ÈXn)|=|X|-(|X1|+…+|Xn|)+(|X1ÇX2|+…+|Xn-1ÇXn|)-+
+(-1)n|X1Ç…ÇXn|. (2.15)
Действительно,
[X\(X1È…ÈXn)]È(X1È…ÈXn)=X,
[X\(X1È…ÈXn)]Ç(X1È…ÈXn)=Æ,
Откуда
|X\(X1È…ÈXn)|+|X1È…ÈXn|=|X|,
А, следовательно,
|X\(X1È…ÈXn)|=|X|-|X1È…ÈXn|. (2.16)
Для получения (2.15) остается только подставить (2.14) в (2.16).
Более распространенная форма записи формулы включений и исключений может быть получена при рассмотрении конечного множества X, такого что |X|=n и заданных свойств a1,…,ak, которыми элементы X могут обладать или не обладать.
Обозначим: – множество элементов в Х, обладающих свойством
- количество элементов в
, обладающих одновременно свойствами
;
- количество элементов в
, не обладающих ни одним из свойств
. Тогда по формуле (2.15) получаем
, (2.17)
Где
Задача 2.11. Пусть Х={0,1,...,10}; : «
– чётные»;
: «
»,
: «
». Найти количество
элементов в
, не обладающих свойствами
.
Решение. Используя формулу (2.15) и (2.17) получаем , в следствии того, что
,
,
,
. Очевидно, что этим единственным элементом в
является число 1.
Задача 2.12. (Задача о беспорядках). Имеется n различных предметов и столько же различных ячеек
. Сколькими способами можно разложить предметы по ячейкам так, чтобы никакой предмет
не попал в ячейку
?
Решение. Роль исходного множества выполнит множество всевозможных распределений по ячейкам. Число таких множеств равно числу перестановок
. Введём свойства ai: «
находится в ячейке
»,
. Число
расположений, при которых
находится в ячейке
,
равно
. Тогда
Используя формулу включений и исключений, получаем число распределений, при которых ни одно из свойств не выполняется, и оно равно: