Формулы включений и исключений

Мощностью конечного множества называется количество элементов в нем. Если множество А имеет n элементов, то пишут

Пусть имеется два пересекающихся множества А и В. Изобразим их на диаграмме Венна. Тогда имеет место следующая формула:

A

B

 

 

Для трех пересекающихся множеств выполняется:

A

B

C

 

Пример 2.9. В месяце было 12 дождливых, 8 ветреных, 4 холодных дня, дождливых и ветреных – 5, дождливых и холодных – 3, ветреных и холодных – 2, дождливых, ветреных и холодных – 1 день. Сколько дней была плохая погода?

Пусть А – дождливые дни, В – ветреные дни, С – холодные, D – дни с плохой погодой. Тогда . Количество дней с плохой погодой:

В общем случае формула включений и исключений для k множеств имеет вид:

Пусть множество А состоит из N элементов и имеется n одноместных отношений (свойств) . Каждый элемент множества может обладать или не обладать любым из этих свойств. Обозначим через число элементов, обладающих свойствами и, может быть, некоторыми другими. Тогда число N (0) элементов, не обладающих ни одним из свойств , вычисляется по следующей формуле:

, где

Обобщая, получаем формулу, позволяющую вычислить число N (r) элементов, обладающих ровно r свойствами .

(1)

Определим функцию [ x ] для вещественных чисел как наибольшее целое число, не превосходящее x. Число [ x ] называется целой частью числа x. Для положительных чисел а и b значение функции равно количеству чисел из множества {1, 2,…, b }, которые делятся на а, т.е. кратны а.

Пример 2.10. Сколько положительных трехзначных чисел делятся ровно на одно из чисел 3, 5 или 7?

Обозначим P₃ – свойство делимости на 3, P₅ – на 5, P₇ – на 7. Тогда

Так как N_3,5 – число чисел, делящихся одновременно на 3 и 5, а наименьшее общее кратное 3 и 5 равно 15, то . Аналогично,

По формуле (1) находим искомое число чисел: