Математика. Комбинаторика. Формула включений и исключений. Примеры + решения.
Формула включений-исключений (или принцип включений-исключений) — комбинаторная формула, позволяющая определить мощность объединения конечного числа конечных множеств, которые в общем случае могут пересекаться друг с другом. В теории вероятностей аналог принципа включений-исключений известен как формула Пуанкаре.
Случай двух множеств
Например, в случае двух множеств формула включений-исключений имеет вид:
В сумме элементы пересечения учтены дважды, и чтобы компенсировать это мы вычитаем из правой части формулы. Справедливость этого рассуждения видна из диаграммы Эйлера-Венна для двух множеств, приведенной на рисунке справа. Таким же образом и в случае множеств процесс нахождения количества элементов объединения состоит во включении всего, затем исключении лишнего, затем включении ошибочно исключенного и так далее, то есть в попеременном включении и исключении. Отсюда и происходит название формулы.
Пусть задано конечное множество А. Число его элементов обозначим n(А). Найдем сколько элементов содержится в множестве А ∪ В. Основная формула нахождения числа элементов суммы двух множеств
n(А ∪ В) = n(А) + n(В) – n(А ∩ В) (1)
Действительно, n(А ∪ В) — это сумма числа элементов множеств А и В, но при подсчете элементы, принадлежащие А ∩ В учитывались дважды. С помощью формулы (1) можно получить формулы для определения числа элементов суммы любого числа множеств. Например,
n(А ∪ В ∪ С) = n(А ∪ (В ∪ С)) = n(А) + n(В ∪ С) – n(А ∩ (В ∪ С)) =
= n(А) + n(В) + n(С) – n(В ∩ С) – n((А ∩ В) ∪ (А ∩ С)) =
= n(А) + n(В) + n(С) – n(В ∩ С) – (n(А ∩ В) + n(А ∩ С) – n((А ∩ В) ∩ (А ∩ С))) =
=n(А) + n(В) + n(С) – n(В ∩ С) – n(А ∩ В) – n(А ∩ C) + n(А ∩ В ∩ С).
n(А ∪ В ∪ С) = n(А) + n(В) + n(С) – n(А ∩ В) – n(В ∩ С) – n(А ∩ C) + n(А ∩ В ∩ С) (2)
Формулы (1) и (2) называют формулами включений и исключений.
Примеры с подробным решением.
Задача 1. Из 100 школьников английский знают 42, немецкий — 30, французский — 28, английский и немецкий — 5, английский и французский — 10, немецкий и французский — 8, английский, немецкий и французский — 3 школьника. Сколько школьников не знают ни одного языка?
Решение. I способ.
Обозначим через А — множество школьников, знающих английский язык; N — множество школьников, знающих немецкий язык; F — множество школьников, знающих французский язык.
Тогда n(A) = 42, n(N) = 30, n(F) = 28, n(A ∩ N) = 5,
n(A ∩ F) = 10, n(N ∩ F) = 8, n(A ∩ N ∩ F) = 3.
Найдем с помощью формулы включений и исключений количество школьников, знающих хотя бы один из перечисленных иностранных языков.
n(A ∪ N ∪ F) = n(A) + n(N) + n(F) =
= n(A ∩ N) – n(A ∩ F) – n(N ∩ F) + n(A ∩ N ∩ F) =
= 42 + 30 + 28 – 5 – 10 – 8 + 3 = 80.
Следовательно, не знают ни одного иностранного языка:
100 – 80 = 20 школьников.
II способ.
Эту же задачу можно решить с помощью диаграммы Эйлера-Венна (рис. 1).
Так как 3 языка знают 3 школьника, то английский и немецкий знают 5 – 3 = 2, английский и французский — 10 – 3 = 7,
немецкий и французский — 8 – 3 = 5 школьников.
Только английский знают 42 –(2 + 3 + 7) = 30,
только немецкий — 30 – (2 + 3 + 5) = 20,
только французский — 28 – (3 + 5 + 7) = 13 школьников.
Ни одного языка не знают 100 – (2 + 3 + 5 + 7 + 13 + 20 + 30) = 20 школьников.
Задача 2. Сколько двузначных чисел не делятся ни на 2, ни на 3, ни на 5, ни на 11?
Решение. Обозначим: А — множество двузначных чисел, делящихся на 2;
В — множество двузначных чисел, делящихся на 3;
С — множество двузначных чисел, делящихся на 5;
D — множество двузначных чисел, делящихся на 11.
n(A ∪ B ∪ C ∪ D) — количество двузначных чисел, делящихся хотя бы на одно из чисел 2; 3; 5; 11.
n(A ∪ B ∪ C ∪ D) = n(A) + n(B) + n(C) + n(D) –
– n(A ∩ B) – n(A ∩ C) – n(A ∩ D) – n(B ∩ C) –
– n(B ∩ D) – n(C ∩ D) + n(A ∩ B ∩ C) + n(A ∩ B ∩ D) +
+ n(A ∩ C ∩ D) + n(B ∩ C ∩ D) – n(A ∩ B ∩ C ∩ D).
n(A) = 45, n(B) = 30, n(C) = 18, n(D) = 9,
n(A ∩ B) = 15, n(A ∩ C) = 9, n(A ∩ D) = 4, n(B ∩ C) = 6,
n(B ∩ D) = 3, n(C ∩ D) = 1, n(A ∩ B ∩ C) = 3,
n(A ∩ B ∩ D) = 1, n(A ∩ C ∩ D) = n(B ∩ C ∩ D) = n(A ∩ B ∩ C ∩ D) = 0.
Итак, n(A ∪ B ∪ C ∪ D) = 45 + 30 +18 + 9 – 15 – 9 – 4 – 6 – 3 – 1 + 3 + 1 = 68.
Так как всего 90 двузначных чисел, то чисел, не делящихся ни на одно из заданных чисел:
90 – 68 = 22.
Задача 3. Известно, что из n учеников спортом увлекаются a учеников, программированием b, математикой c, спортом и программированием d, спортом и математикой e, программированием и математикой f , спортом, математикой и программированием g учеников. Сколько учеников увлекается только программированием? Сколько учеников увлекается только математикой? Сколько учеников ничем не увлекается?
Вариант | n | a | b | c | d | e | f | g |
14 | 70 | 32 | 21 | 23 | 8 | 12 | 4 | 3 |
Решение.
Пусть A —множество учеников, которые увлекаются спортом,
B — программированием, С — математикой.
Тогда |A| = 32, |B| = 21, |C| = 23, |A ∩ B| = 8, |A ∩ C| = 12, |B ∩ C| =4 |A ∩ B ∩ C| = 3
|(A ∩ B) ∪ ( B ∩ C) | = |A ∩ B| + |B ∩ C| − |A ∩ B ∩ C| = 8 + 4 – 3 = 9
Тогда, только программированием занимается 21 – 9 = 12 учеников.
|(A ∩ C) ∪ ( B ∩ C) | = |A ∩ C| + |B ∩ C| − |A ∩ B ∩ C| = 12 + 4 – 3 = 13
Тогда, только математикой занимается 23 – 13 = 10 учеников.
По формуле включений и исключений для трёх множеств находим число учеников увлекающихся спортом, программированием или математикой:
|A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B∩ C| = =32+21+23-8-12-4+3 = 55
Значит, ничем не увлекается 70 − 55 = 15 человек. Ответ: 15.
Теоретическая информатика в Академическом Университете / Хабр
Я хочу описать историю одного заносчивого и самовлюбленного студента Академического Университета, коим я, конечно, не являюсь, но хорошо представляю его мысли и переживания.
Будем называть этого студента, например, Шурик. На момент поступления Шурика в Академический Университет (АУ), согласно его программистскому резюме, он уже был экспертом в области алгоритмов. Он мастерски владел алгоритмом поиска в глубину, знал несколько методов сортировки массивов, и имел представление о двоичном поиске. Естественно, курс алгоритмов его не интересовал совершенно, да и вообще, мало чему можно научить программиста с пятилетним опытом. Программа теоретической информатики АУ его заинтересовала тем, что в темах по известным ему предметам было слишком много неизвестных ему слов. Но это же Питер, там они и бордюр то странным словом называют, вероятно, и для поиска в глубину красивых слов понавыдумывали. Он тщательно изучил слайды и видеозаписи курсов. Оказалось, что существует какая-то там информатика, которой Шурик не владеет в совершенстве. Шурик собрал книги, носки и пять лет опыта, и отправился в Питер на собеседование. Там он встретил людей, которые могут научить чему-то даже программиста с таким опытом.
Во время учëбы в магистратуре Шурик занимался исследованиями в области схемной сложности и области экспоненциальных алгоритмов. Это действительно очень интересно и, что не менее важно, полезно для поступления в аспирантуру.
Сейчас я передаю слово Шурику, который и расскажет об одном своëм исследовании.
Алгоритмы для NP-трудных задач
NP-трудные задачи — это задачи, часто встречающиеся на практике, для которых неизвестны эффективные алгоритмы решения. Исследование таких задач представляет большой интерес, т.
к. существование эффективного алгоритма для любой из таких задач влечет существование эффективных алгоритмов для всех задач из класса NP. И, наоборот, если мы сможем доказать, что хотя бы для одной из таких задач не существует эффективного алгоритма, то это будет означать, что таких алгоритмов не существует для всех NP-трудных задач. В магистратуре АУ мы исследовали точные и приближенные алгоритмы решения некоторых NP-трудных задач. Например, нам удалось получить новые алгоритмы решения задачи о максимальной выполнимости, задачи о коммивояжëре, и задачи о кратчайшей общей надстроке. Далее я хочу описать один из этих алгоритмов, а именно алгоритм приближëнного решения задачи о коммивояжëре.
NP-трудная задача оптимизации — это NP-трудная задача, в которой среди всех возможных решений нужно выбрать оптимальное в каком-то смысле решение. Например, найти кратчайший цикл, проходящий через каждую вершину заданного взвешенного графа ровно один раз. Возможно, существует множество способов обойти граф, проходя по каждой вершине ровно один раз, но нас интересуют только те обходы, которые минимальны по весу.
Эта задача называется задачей коммивояжëра. Время работы лучших известных алгоритмов для этой задачи в худшем случае примерно равно . Мы занимались ускорением алгоритмов для задач такого рода. Например, алгоритм, который работает за время , позволит решать задачу для больших значений n. Интересно заметить, что покупка компьютера, работающего в 1000 раз быстрее, не даст такого ускорения, как новый алгоритм с меньшей экспонентой во времени выполнения. Существование полиномиального алгоритма для этой задачи повлечет равенство классов P и NP, а доказательство отсутствия такого алгоритма будет означать, что эти классы не равны.Задача коммивояжëра
Гамильтонов цикл графа — это цикл, проходящий по каждой вершине графа ровно один раз. Задача коммивояжёра (traveling salesman problem, TSP) заключается в поиске гамильтонова цикла минимального веса в заданном взвешенном графе. Обозначим через n количество вершин исходного графа, а через M — максимальный вес ребра.
Существует множество методов решения задачи о коммивояжëре на практике, но в этой статье мы будем говорить только о теоретических алгоритмах с доказуемыми оценками на время работы в худшем случае.
Точные алгоритмы решения задачи о коммивояжëре
В 1962 году был разработан алгоритм динамического программирования, решающий TSP за время , но при этом используя экспоненциальную память. Лучший известный алгоритм, использующий лишь полиномиальную память, имеет время работы . Также известны промежуточные результаты, например, для любого , существует алгоритм решения задачи со временем работы , использующий память , где . Известны алгоритмы, основанные на формуле включений-исключений, решающие задачу за время , используя память . скрывает полиномиальные множители от длины входа, т.е. . Для неориентированного случая TSP существует Монте-Карло алгоритм со временем работы и экспоненциально маленькой вероятностью ошибки.
Уже более пятидесяти лет открытыми являются следующие вопросы:
- Существование алгоритма для TSP со временем работы и полиномиальной памятью.
- Существование алгоритма для TSP со временем работы для общего (ориентированного) случая задачи о коммивояжëре.
Приближëнные алгоритмы решения задачи коммивояжëра
Известно, что в предположении , общая TSP не может быть приближена с любым полиномиально вычислимым фактором. То есть, в этом предположении, нельзя найти не только 10-приближение оптимального решения, но и даже n!-приближение. Частный случай, в котором веса рëбер графа удовлетворяют неравенству треугольника, называется метрической задачей коммивояжëра. Для неориентированной метрической задачи известно 1.5-приближение. Ещë для этого частного случая известно, что в предположении , нельзя найти полиномиальный алгоритм с приближением лучше (в ориентированном случае — ). Для ориентированной метрической версии задачи фактор приближения был недавно улучшен до .
Приближение за экспоненциальное время
Мы предлагаем алгоритм, который для любого фиксированного использует шагов и полиномиальную память для вычисления -приближения ориентированной метрической задачи коммивояжёра.
Как было указано выше, лучшее известное полиномиальное приближение даже для неориентированной метрической версии TSP — 1.5 (для ориентированной — ).
Если , то за полиномиальное время не может быть найдено -приближение неориентированной метрической TSP.
Если нам необходимо, например, -приближение, то мы должны использовать точные алгоритмы, которые требуют либо экспоненциальную память, либо время . Экспоненциальные алгоритмы редко используются на практике, но в любом случае, мы способны их запустить и ждать ответа. Однако, если алгоритм использует экспоненциальную память, то мы не имеем возможности даже запустить алгоритм на входах разумного размера.
Предложенный алгоритм может найти -приближение общей TSP за время , используя лишь полиномиальную память.
Разработанный алгоритм использует идею, предложенную для построения полностью полиномиальной приближённой схемы для задачи о рюкзаке в работе Ibarra, Kim. Авторы используют псевдополиномиальный алгоритм для задачи о рюкзаке, работающий за время , где n — количество предметов, а W — вместимость рюкзака.
Полностью полиномиальная схема приближения задачи о рюкзаке сначала делит веса всех предметов на , затем вызывает псевдополиномиальный алгоритм. Полученный ответ может не оказаться оптимальным, т.к. некоторые веса не просто поделены на , но и округлены. Однако простой анализ показывает, что округление не сильно сказывается на результате.
Мы используем похожую идею. Через OPT обозначим оптимальное рещение TSP. Для того, чтобы получить полиномиальный по памяти приближённый алгоритм, мы сначала разделим веса всех рёбер на достаточно большое число , затем запустим точный алгоритм, основанный на формуле включений-исключений. Время работы полученного алгоритма будет равно и длина полученного цикла будет не больше . Теперь мы хотим выбрать так, что и . Метрическая версия TSP может быть приближена за полиномиальное время, например, с фактором . То есть, мы можем найти , что и взять . Тогда полученный алгоритм будет иметь время работы и использовать память . Нам также удалось обобщить этот результат для случая общей (неметрической ориентированной) задачи коммивояжëра.
Принцип включения-исключения: примеры с решениями
Полное понимание принципа включения-исключения в дискретной математике жизненно важно для создания прочного фундамента в теории множеств.
В соответствии с принципом включения-исключения обычно есть два типа вопросов, которые появляются в учебных планах по дискретной математике и на более низком уровне. Вот эти типы вопросов:
- Задается количество элементов в определенных наборах, а также их количество в определенных пересечениях наборов. Затем необходимо определить – к исключение других множеств – количество элементов, живущих в определенном множестве или подмножестве. (Отсюда и «исключающая» часть этого принципа.)
- Второй тип более сложен. Количество элементов, живущих на пересечении множеств, неизвестно и требует определения. Этим неизвестным присваивается алгебраическое число (например, x ), а затем они решаются алгебраически. Часто участвуют три сета.
В этой статье мы обсудим несколько примеров принципа включения-исключения и решения для обоих этих типов. Диаграммы Венна, хотя и не являются обязательными, включены для облегчения концептуализации.
Принцип включения-исключения: пример первый (два набора)
Вопрос:
Среди 50 пациентов, поступивших в больницу, у 25 диагностирована пневмония, у 30 — бронхит и у 10 — пневмония и бронхит. Определите:
(a) Количество пациентов с диагнозом пневмония или бронхит (или и то, и другое).
(b) Количество пациентов, у которых не диагностирована пневмония или бронхит.
Решение:
Первым шагом является формальная идентификация наборов и указание количества элементов в каждом. Это можно сделать исключительно с предоставленной информацией; Расчет не требуется. С помощью этого вопроса о принципе включения-исключения три множества можно определить следующим образом:
Пусть U обозначает всю совокупность пациентов. Пусть P и B обозначают набор пациентов с диагнозом пневмония и бронхит соответственно. Таким образом:
|U| = 50
|P| = 25
|В| = 30
|P ∩ B| = 10
Теперь мы можем построить диаграмму Венна. Есть два набора и, следовательно, два круга. Поскольку мы знаем количество элементов на пересечении P и B ( |P∩B| ), мы можем сначала заполнить это:
Теперь мы можем вычислить, сколько элементов живет только в P, но не |P ∩ B|:
Поскольку |P| = 25 и |P∩B| = 10, имеется 15 (25-10 = 15) элементов, исключающих P.
Следуйте тому же методу, чтобы вычислить количество элементов, живущих только в B, но не |P ∩ B|:
Поскольку | Б| = 30 и |P∩B| = 10, имеется 20 (30-10 = 20) элементов, исключающих B.
Эта новая информация должна быть добавлена к нашей диаграмме Венна следующим образом:
Предварительная работа завершена, и у нас достаточно информации, чтобы ответить на вопросы напрямую:
(а) Определить количество пациентов с диагнозом пневмония или бронхит (или оба).
Это то же самое, что попросить определить |P ∪ B|. Глядя на диаграмму Венна, сформулируйте ответ следующим образом:
|P ∪ B| = 15 + 10 + 20
= 45
Таким образом, у 45 пациентов диагностирована пневмония или бронхит.
К тому же ответу можно прийти, используя принцип включения-исключения напрямую, не обращаясь к диаграмме Венна:
|P ∪ B| = |П| + |Б| – |P ∪ B|
= (25 + 30) – (10)
= 45
Таким образом, у 45 пациентов диагностирована пневмония или бронхит.
(b) Определите количество пациентов, у которых не диагностирована пневмония или бронхит.
Это то же самое, что попросить определить |(P ∪ B)’|. Мы знаем, что всего 50 больных, из них 45 с диагнозом пневмония или бронхит. Используйте это, чтобы решить вопрос:
|U| = 50.
|P ∪ B| = 45
Следовательно,
|(P ∪ B)’|
= 50 – 45 = 5
5 пациентов не диагностированы пневмония или бронхит.
Принцип включения-исключения: пример второй (три набора)
Вопрос:В крупной компании по разработке программного обеспечения работает 100 программистов. Из них 45 владеют Java, 30 — C#, 20 — Python, шесть — C# и Java, один — Java и Python, пятеро — C# и Python, и только один программист владеет всеми тремя вышеперечисленными языками.
Определите количество программистов, не владеющих ни одним из этих трех языков.
Решение:Как и в первой задаче упражнения на принцип включения выше, начните с определения данной информации:
Пусть U обозначает множество всех работающих программистов, а J, C и P обозначают набор программистов, владеющих Java, C# и Python соответственно. Таким образом:
|U| = 100
|J| = 45
|С| = 30
|P| = 20
|J ∩ C| = 6
|J ∩ P| = 1
|C ∩ P| = 5
|J ∩ C ∩ P| = 1
Теперь мы можем использовать диаграмму Венна. Это требует трех кругов, так как задействовано три подхода. Сначала заполните центральное пересечение всех трех кругов: J ∩ C ∩ P. Затем используйте вычитание, чтобы определить мощность остальных участков.
Теперь у нас достаточно информации, чтобы ответить на вопрос:
Определите количество программистов, не владеющих ни одним из этих трех языков.
Другими словами, нам нужно определить мощность дополнения множества J ∪ C ∪ P. (Это обозначается как |(J ∪ C ∪ P)’|). Вычислить |J ∪ C ∪ P| сначала перед определением значения дополнения:
|J ∪ C ∪ P|
= 39 + 5 +20 +4 +15 + 1
= 84
Теперь вычислите дополнение:
|(J ∪ C ∪ P)’ | = |U| – |J ∪ C ∪ P|
= 100 – 84
= 16
16 программистов не владеют ни одним из трех языков.
Принцип включения-исключения: пример третий (три набора)
Этот пример вопроса о принципе включения-исключения можно решить алгебраически.
Вопрос:В большом регионе 350 фермеров. 260 хуторских свеклы, 100 хуторских бататов, 70 хуторских редисов, 40 хуторских свеклы и редьки, 40 хуторских батата и редьки и 30 хуторских свеклы и ямса. Пусть B, Y и R обозначают множество ферм, которые выращивают свеклу, ямс и редис соответственно.
Определите количество фермеров, выращивающих свеклу, ямс и редис.
Буквы для обозначения множеств уже были даны в самом вопросе (в отличие от примера выше). Поэтому мы можем сразу отметить мощность:
|У| = 350
|В| = 260
|Y| = 100
|R| = 70
|B ∩ R| = 40
|Y ∩ R| = 40
|B ∩ Y| = 30
Нам нужно определить мощность пересечения всех трех множеств, которая равна |B ∩ Y ∩ R|. Это неизвестное, которое мы можем определить алгебраически. Заполните диаграмму Венна данной информацией. Используйте x для представления |B ∩ Y ∩ R|.
Пусть x фермеров выращивают свеклу, ямс и редис. То есть пусть |B ∩ Y ∩ R| = x
Now solve for x algebraically:
|U|= 350 = 190 + x + (30 – x ) + x + (40 – x ) + (40 – х ) + 30 + х + х – 10
350 = 320 + x
x = 30
Следовательно, 30 фермеров выращивают свеклу, ямс и редис.
AC Формула включения-исключения
Теперь, когда у нас есть понимание того, что мы подразумеваем под свойством, давайте посмотрим, как мы можем использовать это понятие для обобщения процесса, который мы использовали в первых двух примерах предыдущего раздела.
Пусть \(X\) — множество, а \(\mathcal{P}=\{P_1,P_2,\dots,P_m\}\) — семейство свойств. Тогда для каждого подмножества \(S\subseteq [m]\text{,}\) пусть \(N(S)\) обозначает количество элементов \(X\), которые удовлетворяют свойству \(P_i\) для всех \ (i\in S\text{.}\) Обратите внимание, что если \(S=\emptyset\text{,}\), то \(N(S)=|X|\text{,}\) в качестве каждого элемента \(X\) удовлетворяет каждому свойству в \(S\) (которое не содержит фактических свойств).
Возвращаясь ненадолго к примеру 7.1, где \(P_1\) означает «специальность в области компьютерных наук», а \(P_2\) означает «мужчина», отметим, что \(N(\{1\})=47\ text{,}\), так как в классе есть \(47\) специалистов по информатике. Кроме того, \(N(\{2\})=51\), поскольку \(51\) студентов — мужчины. Наконец, \(N(\{1,2\})=45\), так как в классе есть \(45\) мужчин, специализирующихся в области компьютерных наук.
В примерах из предыдущего раздела мы вычли \(N(S)\) для множеств \(S\) размера \(1\), а затем прибавили обратно \(N(S)\) для множества свойств размера \(2\text{,}\), так как мы вычли количество вещей с обоими свойствами (мужчины, специализирующиеся в области информатики, или решения с обоими \(x_3>7\) и \(x_4’>8\). )) дважды. Символически мы определили, что количество объектов, не удовлетворяющих ни одному из свойств, равно 9.0003
\begin{уравнение*} N(\emptyset) — N(\{1\}) — N(\{2\}) + N(\{1,2\}). \end{уравнение*}
Предположим, что у нас есть три свойства \(P_1,P_2\text{,}\) и \(P_3\text{.}\). Как подсчитать количество объектов, не удовлетворяющих ни одному из свойств? Как и раньше, мы начинаем с вычитания для каждого из \(P_1\text{,}\) \(P_2\text{,}\) и \(P_3\text{.}\). Теперь мы удалили объекты, удовлетворяющие обоим \ (P_1\) и \(P_2\) дважды, поэтому мы должны добавить обратно \(N(\{1,2\})\text{. }\) аналогичным образом, мы должны сделать это для объектов, удовлетворяющих обоим \(P_2 \) и \(P_3\), а также \(P_1\) и \(P_3\text{.}\) Теперь давайте подумаем об объектах, удовлетворяющих всем трем свойствам. Они учитываются в \(N(\emptyset)\text{,}\) исключено трижды с помощью \(N(\{i\})\) членов и трижды складывается обратно с помощью \(N(\{i,j\})\) членов. Таким образом, они все еще учитываются! Таким образом, мы должны еще вычесть \(N(\{1,2,3\})\), чтобы получить желаемое число:
\begin{уравнение*} N(\emptyset) — N(\{1\}) — N(\{2\}) — N(\{3\}) + N(\{1,2\}) + N(\{2,3\}) + N(\{1,3\}) — N(\{1,2,3\}). \end{уравнение*}
Мы можем обобщить это как следующую теорему:
Теорема 7.7. Принцип включения-исключения.
Количество элементов \(X\), которые не удовлетворяют ни одному из свойств в \(\mathcal{P}\), равно 9{|S|}N(S).\tag{7.2.1} \end{equation}
Доказательство.
Проведем индукцию по числу \(m\) свойств. Если \(m=1\text{,}\), то формула сводится к \(N(\emptyset)-N(\{1\})\text{. }\). количество элементов, не удовлетворяющих свойству \(P_1\), равно общему количеству элементов минус число, удовлетворяющее свойству \(P_1\text{.}\)
Теперь предположим справедливость, когда \(m\le k\) для некоторого \(k\ge1\) и рассмотрим случай, когда \(m=k+1\text{.}\) Пусть \(X’=\{x \in X: x\) удовлетворяет \(P_{k+1}\}\) и \(X»=X-X’\) (т. е. \(X»\) — это множество элементов, которые выполняют не удовлетворяет \(P_{k+1}\)). Кроме того, пусть \(\mathcal{Q}=\{P_1,P_2,\dots,P_k\}\text{.}\) Тогда для каждого подмножества \(S\subseteq [k]\text{,}\) пусть \(N'(S)\) подсчитать количество элементов \(X’\), удовлетворяющих свойству \(P_i\) для всех \(i\in S\text{.}\) Кроме того, пусть \(N’ ‘(S)\) подсчитать количество элементов \(X»\), удовлетворяющих свойству \(P_i\) для каждого \(i\in S\text{.}\) Обратите внимание, что \(N(S)= N'(S)+N»(S)\) для каждого \(S\subseteq [k]\text{.}\)
Пусть \(X’_0\) обозначает множество элементов в \(X’\), которые не удовлетворяют ни одному из свойств в \(\mathcal{Q}\) (другими словами, те, которые удовлетворяют только \(P_{ k+1}\) из \(\mathcal{P}\)), и пусть \(X»_0\) обозначает множество элементов \(X»\), которые не удовлетворяют ни одному из свойств в \( \mathcal{Q}\text{,}\) и, следовательно, ни одно из свойств в \(\mathcal{P}\text{.