Что такое формула включения исключения: определение термина
Формула из комбинаторики и теории множеств для вычисления мощности объединения множеств. Ее используют, когда нужно узнать, сколько объектов подходит хотя бы под одно из условий. Смысл в том, что при сложении количеств по отдельным условиям общие элементы учитываются несколько раз.
Поэтому их нужно вычесть, а если множеств больше двух, то некоторые пересечения вычитаются слишком много раз и их приходится снова прибавлять. В итоге получается чередование знаков «плюс» и «минус». Эта формула помогает избегать ошибок в задачах на подсчет.
Как работает формула включения исключения
Для двух множеств A и B формула выглядит так: |A ∪ B| = |A| + |B| − |A ∩ B|. Мы складываем элементы A и B, но затем вычитаем пересечение, потому что оно было учтено дважды. Для трех множеств добавляется следующий шаг: сначала складывают мощности, потом вычитают попарные пересечения, а затем прибавляют тройное пересечение.
Такой принцип продолжается и для большего числа множеств, где пересечения учитываются с чередующимися знаками. Формула включения исключения применяется в задачах про учеников, которые посещают разные кружки, про числа с несколькими свойствами, про вероятность событий и про подсчет вариантов в комбинаторике.
