Комбинаторика
  • Регистрация
1 1 1 1 1 1 1 1 1 1 Рейтинг 0.00 (0 Голоса)

Если 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: « находится в ячейке », . Число расположений, при которых находится в ячейке , равно . Тогда

Используя формулу включений и исключений, получаем число распределений, при которых ни одно из свойств не выполняется, и оно равно:

Добавить комментарий


Защитный код
Обновить