Формула включений и исключений
На этой странице мы собрали примеры решения учебных задач на применение принципа включений-исключений в комбинаторных задачах по теории вероятностей или дискретной математике.
Краткая теория
Формула включений и исключений для двух множеств
Для любых конечных множеств $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 объектов. Сколько всего объектов?
Задача 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 не умеют ни плавать, ни играть в шахматы. Определить количество ребят, умеющих плавать и играть в шахматы.
Видеоурок: Формула включений и исключений
Решебник по терверу и комбинаторике
Если решения нужны срочно и недорого? Ищите в решебнике по теории вероятностей:
