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

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


Понравилось? Добавьте в закладки

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

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

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

$$ | A \cup B | =|A|+|B|-|A\cap B|. $$

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

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

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

$$ | A \cup B \cup C | =|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B \cap C|. $$

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

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

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

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

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

Решение: формула включений-исключений для 3 множеств

Задача 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 – французский. Сколько туристов знают оба эти языка?

Решение по формуле включений-исключений для 2 множеств

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

Решение на ФВИ

Мы отлично умеем решать задачи по теории вероятностей

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


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

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