Математика. Комбинаторика. Формула включений и исключений. Примеры + решения.

Формула включений-исключений (или принцип включений-исключений) — комбинаторная формула, позволяющая определить мощность объединения конечного числа конечных множеств, которые в общем случае могут пересекаться друг с другом. В теории вероятностей аналог принципа включений-исключений известен как формула Пуанкаре.  

Случай двух множеств

Например, в случае двух множеств  формула включений-исключений имеет вид:

В сумме  элементы пересечения  учтены дважды, и чтобы компенсировать это мы вычитаем  из правой части формулы. Справедливость этого рассуждения видна из диаграммы Эйлера-Венна для двух множеств, приведенной на рисунке справа. Таким же образом и в случае  множеств процесс нахождения количества элементов объединения состоит во включении всего, затем исключении лишнего, затем включении ошибочно исключенного и так далее, то есть в попеременном включении и исключении. Отсюда и происходит название формулы.

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

Пусть задано конечное множество А. Число его элементов обозначим n(А). Найдем сколько элементов содержится в множестве А ∪ В. Основная формула нахождения числа элементов суммы двух множеств

n(А ∪ В) = n(А) + n(В) – n(А ∩ В)        (1)

Действительно, n(А ∪ В) — это сумма числа элементов множеств А и В, но при подсчете элементы, принадлежащие А ∩ В учитывались дважды. С помощью формулы (1) можно получить формулы для определения числа элементов суммы любого числа множеств. Например,

n(А ∪ В ∪ С) = n(А ∪ (В ∪ С)) = n(А) + n(В ∪ С) – n(А ∩ (В ∪ С)) =

= n(А) + n(В) + n(С) – n(В ∩ С) – n((А ∩ В) ∪ (А ∩ С)) =

= n(А) + n(В) + n(С) – n(В ∩ С) – (n(А ∩ В) + n(А ∩ С) – n((А ∩ В) ∩ (А ∩ С))) =

=n(А) + n(В) + n(С) – n(В ∩ С) – n(А ∩ В) – n(А ∩ C) + n(А ∩ В ∩ С).

n(А ∪ В ∪ С) = n(А) + n(В) + n(С) – n(А ∩ В) – n(В ∩ С) – n(А ∩ C) + n(А ∩ В ∩ С)    (2)

Формулы (1) и (2) называют формулами включений и исключений.

Примеры с подробным решением.

Задача 1. Из 100 школьников английский знают 42, немецкий — 30, французский — 28, английский и немецкий — 5, английский и французский — 10, немецкий и французский — 8, английский, немецкий и французский — 3 школьника. Сколько школьников не знают ни одного языка?

Решение. I способ.

Обозначим через А — множество школьников, знающих английский язык; N — множество школьников, знающих немецкий язык; F — множество школьников, знающих французский язык.

Тогда n(A) = 42, n(N) = 30, n(F) = 28, n(A ∩ N) = 5,

n(A ∩ F) = 10, n(N ∩ F) = 8, n(A ∩ N ∩ F) = 3.

Найдем с помощью формулы включений и исключений количество школьников, знающих хотя бы один из перечисленных иностранных языков.

n(A ∪ N ∪ F) = n(A) + n(N) + n(F) =

= n(A ∩ N) – n(A ∩ F) – n(N ∩ F) + n(A ∩ N ∩ F) =

= 42 + 30 + 28 – 5 – 10 – 8 + 3 = 80.

Следовательно, не знают ни одного иностранного языка:

100 – 80 = 20 школьников.

II способ.

Эту же задачу можно решить с помощью диаграммы Эйлера-Венна (рис. 1).

Так как 3 языка знают 3 школьника, то английский и немецкий знают 5 – 3 = 2, английский и французский — 10 – 3 = 7,

немецкий и французский — 8 – 3 = 5 школьников.

Только английский знают 42 –(2 + 3 + 7) = 30,

только немецкий — 30 – (2 + 3 + 5) = 20,

только французский — 28 – (3 + 5 + 7) = 13 школьников.

Ни одного языка не знают 100 – (2 + 3 + 5 + 7 + 13 + 20 + 30) = 20 школьников.

Задача 2. Сколько двузначных чисел не делятся ни на 2, ни на 3, ни на 5, ни на 11?

Решение. Обозначим: А — множество двузначных чисел, делящихся на 2;

В — множество двузначных чисел, делящихся на 3;

С — множество двузначных чисел, делящихся на 5;

D — множество двузначных чисел, делящихся на 11.

n(A ∪ B ∪ C ∪ D) — количество двузначных чисел, делящихся хотя бы на одно из чисел 2; 3; 5; 11.

n(A ∪ B ∪ C ∪ D) = n(A) + n(B) + n(C) + n(D) –

– n(A ∩ B) – n(A ∩ C) – n(A ∩ D) – n(B ∩ C) –

– n(B ∩ D) – n(C ∩ D) + n(A ∩ B ∩ C) + n(A ∩ B ∩ D) +

+ n(A ∩ C ∩ D) + n(B ∩ C ∩ D) – n(A ∩ B ∩ C ∩ D).

n(A) = 45, n(B) = 30, n(C) = 18, n(D) = 9,

n(A ∩ B) = 15, n(A ∩ C) = 9, n(A ∩ D) = 4, n(B ∩ C) = 6,

n(B ∩ D) = 3, n(C ∩ D) = 1, n(A ∩ B ∩ C) = 3,

n(A ∩ B ∩ D) = 1, n(A ∩ C ∩ D) = n(B ∩ C ∩ D) = n(A ∩ B ∩ C ∩ D) = 0.

Итак, n(A ∪ B ∪ C ∪ D) = 45 + 30 +18 + 9 – 15 – 9 – 4 – 6 – 3 – 1 + 3 + 1  = 68.

Так как всего 90 двузначных чисел, то чисел, не делящихся ни на одно из заданных чисел:

90 – 68 = 22.

Задача 3. Известно, что из n учеников спортом увлекаются a учеников, программированием b, математикой c, спортом и программированием d, спортом и математикой e, программированием и математикой f , спортом, математикой и программированием g учеников. Сколько учеников увлекается только программированием? Сколько учеников увлекается только математикой? Сколько учеников ничем не увлекается?

Решение. Пусть A —множество учеников, которые увлекаются спортом,

B — программированием, С - математикой.

Тогда |A| = 32, |B| = 21, |C| = 23, |A ∩ B| = 8, |A ∩ C| = 12, |B ∩ C| =4 |A ∩ B ∩ C| = 3

|(A ∩ B) ∪ ( B ∩ C) | = |A ∩ B| + |B ∩ C| − |A ∩ B ∩ C| = 8 + 4 – 3 = 9

Тогда, только программированием занимается 21 – 9 = 12 учеников.

|(A ∩ C) ∪ ( B ∩ C) | = |A ∩ C| + |B ∩ C| − |A ∩ B ∩ C| = 12 + 4 – 3 = 13

Тогда, только математикой занимается 23 – 13 = 10 учеников.

По формуле включений и исключений для трёх множеств находим число учеников увлекающихся спортом, программированием или математикой:

|A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B∩ C| = =32+21+23-8-12-4+3 = 55

Значит, ничем не увлекается 70 − 55 = 15 человек. Ответ: 15.