В чем заключается комбинаторный принцип включения-исключения?

Принцип включения-исключения в комбинаторике помогает вычислить количество элементов, у которых есть хотя бы одно из нескольких свойств. 1 При этом элементы, у которых есть более чем одно свойство, не учитываются дважды. 1

Суть принципа: чтобы посчитать размер объединения нескольких множеств, нужно просуммировать размеры этих множеств по отдельности, затем вычесть размеры всех попарных пересечений этих множеств, прибавить обратно размеры пересечений всевозможных троек множеств, вычесть размеры пересечений четвёрок и так далее, вплоть до пересечения всех множеств. 4

Пример: нужно найти число людей, у которых есть хотя бы одна кошка или собака. 1 Известно, что у пяти человек есть кошка, а у восьми — собака, а у трёх из них есть и кошка, и собака. 1 Решение: 5 + 8 - 3 = 10 — число людей, у которых есть хотя бы одна кошка или одна собака. 1

Принцип включения-исключения полезен в комбинаторике и теории вероятности, так как гарантирует, что объект не посчитается дважды. 1