Почему формула включений-исключений эффективна для подсчета пересечений множеств?

Формула включений-исключений эффективна для подсчёта пересечений множеств, потому что позволяет определить мощность объединения конечного числа множеств, которые в общем случае могут пересекаться друг с другом. foxford.ru

Например, в случае двух множеств A и B в сумме |A| + |B| элементы пересечения A ∩ B учтены дважды. neerc.ifmo.ru foxford.ru Чтобы компенсировать это, из правой части формулы вычитают мощность пересечения, чтобы каждый элемент был подсчитан ровно один раз. neerc.ifmo.ru foxford.ru

Для случая с большим количеством рассматриваемых множеств процесс нахождения количества элементов объединения состоит в поочерёдном включении ошибочно исключённого и исключении ошибочно включённого, то есть в попеременном включении и исключении. neerc.ifmo.ru foxford.ru Отсюда и происходит название формулы. neerc.ifmo.ru foxford.ru