Все формулы РФ

Математика / Графы, логика

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

Формула включений и исключений для трех множеств считает элементы, попавшие хотя бы в одно из 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$
третье конечное множество или третий признак в том же универсуме, элемент

Условия применения

  • Множества A, B и C должны быть конечными подмножествами одного и того же универсума.
  • Попарные пересечения A∩B, A∩C и B∩C считают вместе с элементами тройного пересечения, если условие не говорит иначе.
  • Тройное пересечение A∩B∩C должно быть известно отдельно или выводиться из дополнительных данных.

Ограничения

  • Если в условии даны области «только A и B», их нельзя автоматически подставлять как полные попарные пересечения.
  • Формула считает элементы хотя бы с одним из трех признаков; для ровно одного или ровно двух признаков нужно дополнительное разбиение областей.
  • Для четырех и более множеств знаки продолжают чередоваться, поэтому формулу для трех множеств нельзя просто обрезать или копировать без нового члена.

Подробное объяснение

Формула для трех множеств считает объединение A∪B∪C, то есть все элементы, которые имеют хотя бы один из трех признаков. Первый шаг естественный: сложить |A|, |B| и |C|. Но элементы из попарных пересечений при таком сложении учитываются больше одного раза, поэтому формула вычитает |A∩B|, |A∩C| и |B∩C|.

Особенность трех множеств в центральной области A∩B∩C. Элемент, который лежит во всех трех множествах, сначала попадает в сумму трех мощностей три раза. Затем он входит в каждое из трех попарных пересечений и вычитается три раза. После этих действий его вклад равен нулю, поэтому тройное пересечение нужно добавить обратно один раз.

Попарные пересечения в формуле понимаются как полные пересечения, включая элементы из тройного пересечения. Если в условии написано «только A и B», это уже другая область диаграммы Венна, и ее нельзя без пересчета подставлять вместо |A∩B|. Такая путаница особенно часто возникает в задачах с опросами и анкетами.

Диаграмма Венна для трех множеств разбивает универсум на восемь областей: вне всех множеств и семь областей внутри объединения. Формула включений и исключений собирает эти семь внутренних областей так, чтобы каждая из них дала вклад ровно один. Поэтому она удобна не только для ответа «хотя бы один признак», но и как основа для последующего подсчета «ровно один» или «ровно два».

От формулы для двух множеств этот случай отличается последним добавлением. Именно тройное пересечение показывает общий принцип чередования знаков: одиночные множества включаются, попарные пересечения исключаются, пересечение трех снова включается. Для большего числа множеств эта логика продолжается.

Как пользоваться формулой

  1. Задайте общий универсум и три множества A, B и C.
  2. Запишите мощности трех множеств и трех попарных пересечений.
  3. Сложите |A|, |B| и |C|, затем вычтите попарные пересечения.
  4. Добавьте |A∩B∩C|, чтобы вернуть центральную область диаграммы.
  5. Проверьте, что каждую из семи внутренних областей учли ровно один раз.

Историческая справка

Принцип включений и исключений вырос из задач о пересекающихся классах объектов и событиях вероятности. Для двух событий идея вычитания общего пересечения появляется почти сразу, но для трех и большего числа множеств становится видна общая закономерность чередования знаков. В исторической литературе разные формы этого принципа связывают с развитием комбинаторики и вероятности от де Муавра до работ XIX века.

В XIX-XX веках язык множеств, булева алгебра и комбинаторные методы сделали запись с A∪B∪C стандартной. Формула для трех множеств заняла важное место в учебниках, потому что она показывает центральную идею принципа лучше, чем случай двух множеств: после вычитания попарных пересечений появляется необходимость вернуть тройное пересечение.

Историческая линия формулы

Формула для трех множеств является частью общего принципа включений и исключений, а не отдельным изобретением одного автора. Ее обычно рассматривают как результат развития вероятностного счета, комбинаторики и теории множеств; современная школьно-университетская запись закрепилась вместе с обозначениями объединения и пересечения.

Пример

Задача: в опросе 60 студентов 30 выбрали математику, 24 - программирование, 18 - физику. При этом математику и программирование выбрали 12 человек, математику и физику - 9, программирование и физику - 7, а все три направления - 4. Сколько студентов выбрали хотя бы одно направление? Обозначим множества через A, B и C. Подстановка: |A∪B∪C|=30+24+18-12-9-7+4=50. Ответ: хотя бы одно направление выбрали 50 студентов. Проверка: центр диаграммы с 4 студентами сначала попал в сумму три раза, затем был вычтен из трех попарных пересечений, поэтому добавление 4 возвращает его ровно один раз; вне объединения осталось 10 студентов.

Частая ошибка

В случае трех множеств самая частая ошибка - остановиться после вычитания попарных пересечений и забыть добавить |A∩B∩C|. Элемент, попавший во все три множества, сначала считается три раза, затем вычитается три раза, поэтому его нужно вернуть один раз. Также важно помнить, что попарные пересечения обычно уже включают тройное пересечение. Если даны числа «только A и B», их нельзя без проверки подставлять как |A∩B|.

Практика

Задачи с решением

Подсчитать участников трех секций

Условие. |A|=14, |B|=12, |C|=9, |A∩B|=5, |A∩C|=4, |B∩C|=3, |A∩B∩C|=2.

Решение. Подставляем: 14+12+9-5-4-3+2=25.

Ответ. Хотя бы одну из трех секций посещают 25 человек.

Понять роль тройного пересечения

Условие. Один элемент лежит сразу в A, B и C.

Решение. В сумме трех множеств он учтен 3 раза, в трех попарных пересечениях вычтен 3 раза, затем добавлен 1 раз.

Ответ. Итоговый вклад центрального элемента равен 1.

Дополнительные источники

  • Graham R. L., Knuth D. E., Patashnik O. Concrete Mathematics
  • Rosen K. H. Discrete Mathematics and Its Applications
  • van Lint J. H., Wilson R. M. A Course in Combinatorics

Связанные формулы

Математика

Правило суммы в комбинаторике

$N=m_1+m_2+\cdots+m_k$

Формула описывает прием «сложение несовместных случаев» для подсчета конечных объектов без полного перебора. Она фиксирует, что именно считается: случаи, шаги, группы, пересечения, рекуррентные члены или пары вершин, и помогает избежать двойного счета.

Математика

Правило произведения в комбинаторике

$N=m_1m_2\cdots m_k$

Формула описывает прием «умножение последовательных шагов» для подсчета конечных объектов без полного перебора. Она фиксирует, что именно считается: случаи, шаги, группы, пересечения, рекуррентные члены или пары вершин, и помогает избежать двойного счета.

Математика

Число перестановок без повторений

$P_n=n!$

Формула описывает прием «перестановки разных объектов» для подсчета конечных объектов без полного перебора. Она фиксирует, что именно считается: случаи, шаги, группы, пересечения, рекуррентные члены или пары вершин, и помогает избежать двойного счета.

Математика

Число размещений без повторений

$A_n^k=\frac{n!}{(n-k)!}$

Формула описывает прием «упорядоченный выбор» для подсчета конечных объектов без полного перебора. Она фиксирует, что именно считается: случаи, шаги, группы, пересечения, рекуррентные члены или пары вершин, и помогает избежать двойного счета.

Математика

Число сочетаний без повторений

$C_n^k=\binom nk=\frac{n!}{k!(n-k)!}$

Формула описывает прием «неупорядоченный выбор» для подсчета конечных объектов без полного перебора. Она фиксирует, что именно считается: случаи, шаги, группы, пересечения, рекуррентные члены или пары вершин, и помогает избежать двойного счета.