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

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

Некоторые области практического применения формулы:

• Вычисление количества элементов, у которых есть хотя бы одно из нескольких свойств. 2 При этом элементы, у которых есть более чем одно свойство, не учитываются дважды. 2 Например, можно найти число людей, у которых есть хотя бы одна кошка или собака, если известно, что у пяти человек есть кошка, а у восьми — собака, а у трёх из них есть и кошка, и собака. 2
• Решение задач о перестановках. 14 Например, можно посчитать, сколько есть перестановок чисел от 0 до 9 таких, что первый элемент больше 1, а последний — меньше 8. 1
• Определение количества чисел в заданном отрезке, кратных хотя бы одному из заданных чисел. 1
• Вычисление количества строк, удовлетворяющих заданному числу паттернов. 1
• Решение задач о путях. 1 Например, можно посчитать число способов дойти от одной клетки до другой, избежав всех препятствий. 1
• Вычисление функции Эйлера. 45 Формула позволяет найти явное выражение для функции, выражающей количество чисел, взаимно простых с определённым числом. 4