Формула включений и исключений для трех множеств

Формула включений и исключений для трех множеств

На этой странице мы собрали примеры решения учебных задач на применение принципа включений-исключений в комбинаторных задачах по теории вероятностей или дискретной математике.

Краткая теория

Формула включений и исключений для двух множеств

Для любых конечных множеств $A$ и $B$ справедливо равенство:

В сумме $|A|+|B|$ пересечение $Acap B$ учтено дважды, поэтому для компенсации мы вычитаем $|Acap B|$.

Формула включений и исключений для трех множеств

Для любых конечных множеств $A$, $B$ и $C$ справедливо равенство:

$$ | A cup B cup C | =|A|+|B|+|C|-|Acap B|-|Acap C|-|Bcap C|+|Acap B cap C|. $$

Поясним кратко, откуда берутся слагаемые справа. Назовём двукратными элементы, входящие в пересечение ровно двух множеств, и трёхкратными — элементы, входящие в пересечение трёх множеств. Сложив мощности $A$, $B$ и $C$, мы дважды учли каждый двукратный элемент и трижды — каждый трёхкратный. Вычтя три попарных пересечения, мы «восстановили справедливость» в отношении двукратных элементов, но при этом трижды вычли трехкратные элементы, которые теперь оказались полностью неучтёнными. Поэтому надо добавить мощность тройного пересечения.

Разберем примеры решений типовых задач с этой формулой включений и исключений для случая 2 и 3 множеств (другие примеры подобных заданий вы найдете в разделе Примеры по дискретной математике: Множества и отношения).

Примеры решенных задач

Задача 1. Формула включений и исключений (для трех множеств). Известно, что свойством А обладает n объектов, В — m объектов, С — с объектов, АВ — р объектов, АС — g объектов, ВС — r объектов, АВС — q объектов. Сколько всего объектов?

Задача 2. Из 100 человек студентов, сдавших сессию, 48 человек сдали экономику, 42 студента – математику и 37 человек – логику. По экономике или математике сдали экзамен 76 человек, по экономике или логике также 76 человек, а по математике или логике – 66 человек. Сколько человек сдали хотя бы один экзамен, если все три предмета сдали 5 человек? Сколько человек не сдали ни одного экзамена? Сколько человек сдали только один экзамен по логике?

Задача 3. При обследовании читательских вкусов студентов оказалось, что 60 % студентов читают журнал А, 50 % — журнал В, 50 % — журнал С, 30 % — журналы А и В, 20 % — журналы В и С, 40 % — журналы А и С, 10 % — журналы А, В и С. Выяснить, сколько процентов студентов:
1) не читает ни одного из журналов;
2) читает в точности два журнала;
3) читает не менее двух журналов.

Задача 4. На одной из кафедр университета работают 13 человек, причем каждый из них знает хотя бы один иностранный язык. Десять человек знают английский, семеро — немецкий, шестеро — французский, пятеро знают английский и немецкий, четверо — английский и французский, трое — немецкий и французский. Выяснить:
1) сколько человек знают все три языка;
2) сколько человек знают ровно два языка;
3) сколько человек знают только английский язык.

Задача 5. Из 100 туристов, выехавших в заграничное путешествие, 10 человек не знают ни немецкого, ни французского языков, 76 человек знают немецкий и 83 – французский. Сколько туристов знают оба эти языка?

Задача 6. В отряде из 40 ребят 30 умеют плавать; 27 умеют играть в шахматы; 5 не умеют ни плавать, ни играть в шахматы. Определить количество ребят, умеющих плавать и играть в шахматы.

Читайте также:  Рамки для профиля в инстаграме

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

Решебник по терверу и комбинаторике

Если решения нужны срочно и почти даром? Ищите в решебнике по теории вероятностей:

Пусть задано конечное множество А. Число его элементов обозначим 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 школьника. Сколько школьников не знают ни одного языка?

Обозначим через А — множество школьников, знающих английский язык; 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 школьников.

Эту же задачу можно решить с помощью диаграммы Эйлера–Венна (рис. 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;

Читайте также:  Чем можно открыть mdf файл

С — множество двузначных чисел, делящихся на 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 двузначных чисел, то чисел, не делящихся ни на одно из заданных чисел:

Задача 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.

1. В спортивном классе обучаются 24 человека. Каждый учащийся занимается хотя бы одним видом спорта (баскетболом или волейболом), из них баскетболом и волейболом занимаются 12 человек. Сколько человек занимается только волейболом, если их в 3 раза больше, чем тех, кто занимается только баскетболом?

2. В одном украинском городе все жители говорят на русском или украинском языке. По-украински говорят 80 % всех жителей, а по-русски — 75 %. Сколько процентов всех жителей говорят на обоих языках?

3. Группа ребят отправилась в поход. Семеро из них взяли с собой бутерброды, шестеро — фрукты, пятеро — печенье. Четве- ро ребят взяли с собой бутерброды и фрукты, трое — бутерброды и печенье, двое — фрукты и печенье, а один — и бутерброды, и фрукты, и печенье. Сколько ребят пошли в поход?

Читайте также:  За счет какой связи

4. Староста класса, в котором 40 человек, подводил итоги по успеваемости группы за I полугодие. Получилась следующая картина: из 40 учащихся не имеют троек по русскому языку 25 человек, по математике — 28 человек, по русскому языку и мате- матике — 16 человек, по физике — 31 человек, по физике и ма- тематике — 22 человека, по физике и русскому языку 16 человек. Кроме того, 12 человек учатся без троек по всем трем предметам. Классный руководитель, просмотрев результаты, сказал: «В тво- их расчетах есть ошибка». Составьте диаграмму Эйлера–Венна и объясните, почему это так.

5. В лаборатории института работают несколько человек. Каждый из них знает хотя бы один иностранный язык. 7 человек знают английский, 7 — немецкий, 8 — французский, 5 знают английский и немецкий, 4 — немецкий и французский, 3 — французский и английский, 2 человека знают все три языка. Сколько человек работает в лаборатории? Сколько из них знает только французский язык? Сколько человек знает ровно 1 язык?

6. Сколько целых чисел от 0 до 999 не делятся ни на 5, ни на 7, ни на 11?

Ответы: 1. 9. 2. 55 %. 3. 10. 4. Если на диаграмме Эйлера– Венна отметить данные в непересекающихся множествах класса, то общее число учащихся класса получится равным 42, а не 40, как сказано в условии. 5. 12; 3; 4. 6. 376.

Часто комбинаторная конфигурация является объединением других, число комбинаций в которых вычислить проще. В таком случае требуется уметь вычислять число комбинаций в объединении.

Пусть А1 и А2 – 2 конечных множества. Тогда если А1ÇА2=Æ, то . Пусть теперь А1ÇА2¹Æ, тогда в каждый элемент из А1ÇА2 будет учтен дважды. Поэтому . Последнюю формулу можно обобщить на случай произвольного числа множеств:

. (2)

Равенство (2) называется формулой включений и исключений. В частности, для трех множеств эта формула имеет вид:

.

Доказывается формула (1) методом математической индукции.

Пример 6.

Сколько существует натуральных чисел, меньших 1000, которые не делятся ни на 3, ни на 5, ни на 7?

Всего чисел, меньших тысячи, 999. Из них 999:3=333 делятся на 3,

999:5=199 (ост. 4) делятся на 5,

999:7=142 (ост. 5) делятся на 7,

999:(3х5)=66 (ост. 9) делятся на 3 и на 5,

999:(3х7)=47 (ост. 12) делятся на 3 и на 7,

999:(5х7)=28 (ост. 10) делятся на 5 и на 7,

999:(3х5х7)=9 (ост. 45) делятся на 3, на 5 и на 7.

В итоге искомых чисел 999-(333+199+142-66-47-28+9)=457.

Следствие.Пусть А – конечное множество, А1, …, Аn – его подмножества. Тогда

. (3)

Доказательство. Поскольку , а Æ, то . Следовательно, . Применив для правой части последнего равенства формулу включений и исключений, получим искомый результат.

Пример 7.

Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: Для студентов недели бывают четные, нечетные и зачетные. 9634 — | 7524 — или читать все.

91.146.8.87 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.

Отключите adBlock!
и обновите страницу (F5)

очень нужно

Ссылка на основную публикацию
Файл cms что это
Файлы формата CMS открываются специальными программами. Существует 2 типа форматов CMS, каждый из которых открывается разными программами. Чтобы открыть нужный...
Унитаз лира киров отзывы
Сырье также используется импортное, тщательно отобранное и экологически чистое — глина, гипс, каолин, полевой шпат, красители. Гарантия на производимые компанией...
Унитаз ресса киров отзывы
Мы предлагаем унитазы росссийского производителя Роза (Киров). В нашем каталоге собрано 30 моделей по цене от 3 090р. Перейдите по...
Файл менеджер для windows 10 на русском
Менеджер файлов осуществляет просмотр, копирование, управление медиафайлами и папками на персональном компьютере. Он предоставляет функцию быстрого перемещения объектов для ускорения...
Adblock detector