Принцип включения-исключения - Inclusion–exclusion principle

Диаграмма Венна показывая объединение множеств А и B как все не в белом

В комбинаторика, филиал математика, то принцип включения-исключения это метод подсчета, который обобщает знакомый метод определения количества элементов в союз из двух конечные множества; символически выражается как

${\displaystyle |A\cup B|=|A|+|B|-|A\cap B|,}$

куда А и B - два конечных множества и |S| указывает на мощность набора S (которое можно рассматривать как количество элементов набора, если набор конечный ). Формула выражает тот факт, что сумма размеров двух наборов может быть слишком большой, поскольку некоторые элементы могут быть пересчитаны дважды. Элементы с двойным счетом - это элементы в пересечение двух наборов, и счет корректируется путем вычитания размера пересечения.

Принцип более отчетливо виден в случае трех наборов, которые для наборов А, B и C дан кем-то

${\displaystyle |A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|.}$

Эту формулу можно проверить, посчитав, сколько раз каждый регион в Диаграмма Венна фигура входит в правую часть формулы. В этом случае при удалении вкладов слишком подсчитанных элементов количество элементов во взаимном пересечении трех наборов вычиталось слишком часто, поэтому их необходимо добавить обратно, чтобы получить правильную сумму.

Включение-исключение, иллюстрируемое диаграммой Венна для трех множеств

Обобщение результатов этих примеров дает принцип включения – исключения. Чтобы найти мощность объединения п наборы:

1. Включите мощности множеств.
2. Исключаем мощности попарных пересечений.
3. Включите мощности тройных пересечений.
4. Исключаем мощности четверных пересечений.
5. Включите мощности пятикратных пересечений.
6. Продолжайте до тех пор, пока мощность п-корочечное пересечение включено (если п нечетное) или исключено (п четное).

Название происходит от идеи, что принцип основан на чрезмерной щедрости. включениес последующим компенсационным исключение.Эту концепцию приписывают Авраам де Муавр (1718);^[1] но впервые он появляется в статье Даниэль да Силва (1854),^[2] а позже в статье Дж. Дж. Сильвестр (1883).^[3] Иногда принцип упоминается как формула Да Силвы или Сильвестра из-за этих публикаций. Принцип является примером ситовый метод широко используется в теория чисел и иногда его называют формула сита,^[4] хотя Лежандр уже использовал подобное устройство в контексте сита в 1808 году.

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

В очень абстрактной постановке принцип включения-исключения может быть выражен как вычисление инверсии определенной матрицы.^[5] Это обратное имеет особую структуру, что делает этот принцип чрезвычайно ценным методом в комбинаторике и смежных областях математики. В качестве Джан-Карло Рота положи это:^[6]

«Одним из наиболее полезных принципов перечисления в дискретной теории вероятностей и комбинаторной теории является знаменитый принцип включения-исключения. При умелом применении этот принцип дал решение многих комбинаторных проблем».

Заявление

В общем виде принцип включения-исключения утверждает, что для конечных множеств А₁, ..., А_п, у одного есть личность

${\displaystyle \left|\bigcup _{i=1}^{n}A_{i}\right|=\sum _{i=1}^{n}|A_{i}|-\sum _{1\leqslant i<j\leqslant n}|A_{i}\cap A_{j}|+\sum _{1\leqslant i<j<k\leqslant n}|A_{i}\cap A_{j}\cap A_{k}|-\cdots +(-1)^{n-1}\left|A_{1}\cap \cdots \cap A_{n}\right|.}$

(1)

Каждый член формулы включения-исключения постепенно корректирует счет, пока, наконец, не каждая часть Диаграмма Венна засчитывается ровно один раз.

Это можно компактно записать как

${\displaystyle \left|\bigcup _{i=1}^{n}A_{i}\right|=\sum _{k=1}^{n}(-1)^{k+1}\left(\sum _{1\leqslant i_{1}<\cdots <i_{k}\leqslant n}|A_{i_{1}}\cap \cdots \cap A_{i_{k}}|\right)}$

или же

${\displaystyle \left|\bigcup _{i=1}^{n}A_{i}\right|=\sum _{\emptyset \neq J\subseteq \{1,\ldots ,n\}}(-1)^{|J|+1}\left|\bigcap _{j\in J}A_{j}\right|.}$

Другими словами, чтобы подсчитать количество элементов в конечном объединении конечных наборов, сначала просуммируйте мощности отдельных наборов, затем вычтите количество элементов, которые появляются по крайней мере в двух наборах, затем добавьте обратно количество элементов, которые появляются в как минимум три набора, затем вычтите количество элементов, которые появляются как минимум в четырех наборах, и так далее. Этот процесс всегда заканчивается, поскольку не может быть элементов, которые встречаются в большем количестве наборов в объединении. (Например, если ${\displaystyle n=4,}$ не может быть элементов, которые появляются более чем в ${\displaystyle 4}$ наборы; эквивалентно, не может быть элементов, которые появляются хотя бы в ${\displaystyle 5}$ наборы.)

В приложениях часто можно увидеть принцип, выраженный в дополнительной форме. То есть позволяя S быть конечным универсальный набор содержащий все А_я и позволяя ${\displaystyle {\bar {A_{i}}}}$ обозначают дополнение А_я в S, к Законы де Моргана у нас есть

${\displaystyle \left|\bigcap _{i=1}^{n}{\bar {A_{i}}}\right|=\left|S-\bigcup _{i=1}^{n}A_{i}\right|=|S|-\sum _{i=1}^{n}|A_{i}|+\sum _{1\leqslant i<j\leqslant n}|A_{i}\cap A_{j}|-\cdots +(-1)^{n}|A_{1}\cap \cdots \cap A_{n}|.}$

В качестве другого варианта утверждения пусть п₁, ..., п_п быть списком свойств, которые элементы набора S может быть или не иметь, то принцип включения – исключения позволяет рассчитать количество элементов S которые не обладают ни одним из свойств. Просто позволь А_я быть подмножеством элементов S которые имеют собственность п_я и использовать принцип в его дополнительной форме. Этот вариант связан с Дж. Дж. Сильвестр.^[1]

Обратите внимание, что если принять во внимание только первые т <п суммы справа (в общем виде принципа), то вы получите завышение, если м является нечетным и недооцененным, если м даже.

Примеры

Подсчет целых чисел

В качестве простого примера использования принципа включения – исключения рассмотрим вопрос:^[7]

Сколько целых чисел в {1, ..., 100} не делятся на 2, 3 или 5?

Позволять S = {1, ..., 100} и п₁ свойство, что целое число делится на 2, п₂ свойство, что целое число делится на 3 и п₃ свойство, что целое число делится на 5. Положив А_я быть подмножеством S чьи элементы имеют свойство п_я по элементарному подсчету имеем: |А₁| = 50, |А₂| = 33 и |А₃| = 20. Всего 16 таких целых чисел делятся на 6, 10 делятся на 10 и 6 делятся на 15. Наконец, есть всего 3 целых числа, делимых на 30, поэтому количество целых чисел не делится ни на одно из 2, 3 или 5. дан кем-то:

100 − (50 + 33 + 20) + (16 + 10 + 6) - 3 = 26.

Подсчет расстройств

Более сложный пример - следующий.

Предположим, есть колода п карты пронумерованы от 1 доп. Предположим, карта пронумерована м находится в правильном положении, если это м-я карта в колоде. Сколько способов, W, можно ли перетасовать карты, если хотя бы одна карта находится в правильном положении?

Начнем с определения набора А_м, который представляет собой все упорядочения карточек с м-я карта правильная. Тогда количество заказов, W, с по меньшей мере одна карта находится в правильном положении, м, является

${\displaystyle W=\left|\bigcup _{m=1}^{n}A_{m}\right|.}$

Применять принцип включения – исключения,

${\displaystyle W=\sum _{m_{1}=1}^{n}|A_{m_{1}}|-\sum _{1\leqslant m_{1}<m_{2}\leqslant n}|A_{m_{1}}\cap A_{m_{2}}|+\cdots +(-1)^{p-1}\sum _{1\leqslant m_{1}<\cdots <m_{p}\leqslant n}|A_{m_{1}}\cap \cdots \cap A_{m_{p}}|+\cdots }$

Каждое значение ${\displaystyle A_{m_{1}}\cap \cdots \cap A_{m_{p}}}$ представляет собой набор тасовок, имеющих не менее п значения м₁, ..., м_п в правильном положении. Обратите внимание, что количество перетасовок не менее п правильные значения зависят только от п, а не на конкретные значения ${\displaystyle m}$. Например, количество перемешиваний с 1-й, 3-й и 17-й картами в правильном положении совпадает с количеством перемешиваний с правильными позициями 2-й, 5-й и 13-й карт. Имеет значение только то, что п карты, 3 были выбраны в правильном положении. Таким образом, есть ${\displaystyle {n \choose p}}$ равные условия в п-е суммирование (см. сочетание ).

${\displaystyle W={n \choose 1}|A_{1}|-{n \choose 2}|A_{1}\cap A_{2}|+\cdots +(-1)^{p-1}{n \choose p}|A_{1}\cap \cdots \cap A_{p}|+\cdots }$

${\displaystyle |A_{1}\cap \cdots \cap A_{p}|}$ это количество заказов, имеющих п элементы в правильном положении, равном количеству способов упорядочения оставшихся п − п элементы, или (п − п) !. Таким образом, окончательно получаем:

${\displaystyle {\begin{aligned}W&={n \choose 1}(n-1)!-{n \choose 2}(n-2)!+\cdots +(-1)^{p-1}{n \choose p}(n-p)!+\cdots \\&=\sum _{p=1}^{n}(-1)^{p-1}{n \choose p}(n-p)!\\&=\sum _{p=1}^{n}(-1)^{p-1}{\frac {n!}{p!(n-p)!}}(n-p)!\\&=\sum _{p=1}^{n}(-1)^{p-1}{\frac {n!}{p!}}\end{aligned}}}$

Перестановка, где нет карта в правильном положении называется психическое расстройство. Принимая п! быть общим числом перестановок, вероятность Q что случайное перемешивание приводит к расстройству

${\displaystyle Q=1-{\frac {W}{n!}}=\sum _{p=0}^{n}{\frac {(-1)^{p}}{p!}},}$

усечение до п + 1 условия Расширение Тейлора из е⁻¹. Таким образом, вероятность угадать порядок перетасованной колоды карт и ошибиться по каждой карте составляет примерно е⁻¹ или 37%.

Особый случай

Ситуация, которая появляется в приведенном выше примере психического расстройства, возникает достаточно часто, чтобы заслужить особого внимания.^[8] А именно, когда размер множеств пересечений, фигурирующих в формулах для принципа включения-исключения, зависит только от количества множеств в пересечениях, а не от того, какие множества появляются. Более формально, если пересечение

${\displaystyle A_{J}:=\bigcap _{j\in J}A_{j}}$

имеет такую ​​же мощность, скажем α_k = |А_J|, для каждого k-элементное подмножество J из {1, ...,п}, тогда

${\displaystyle \left|\bigcup _{i=1}^{n}A_{i}\right|=\sum _{k=1}^{n}(-1)^{k-1}{\binom {n}{k}}\alpha _{k}.}$

Или в дополнительной форме, где универсальный набор S имеет мощность α₀,

${\displaystyle \left|S\setminus \bigcup _{i=1}^{n}A_{i}\right|=\sum _{k=0}^{n}(-1)^{k}{\binom {n}{k}}\alpha _{k}.}$

Обобщение

Учитывая семейство (допускается повторение) подмножеств А₁, А₂, ..., А_п универсального набора S, принцип включения – исключения рассчитывает количество элементов S ни в одном из этих подмножеств. Обобщение этой концепции позволило бы вычислить количество элементов S которые появляются точно в некоторых фиксированных м этих наборов.

Позволять N = [п] = {1,2,...,п}. Если мы определим ${\displaystyle A_{\emptyset }=S}$, то принцип включения – исключения можно записать в виде, используя обозначения предыдущего раздела; количество элементов S не содержится ни в одном из А_я является:

${\displaystyle \sum _{J\subseteq [n]}(-1)^{|J|}|A_{J}|.}$

Если я фиксированное подмножество индексного множества N, то количество элементов, принадлежащих А_я для всех я в я и ни для каких других значений:^[9]

${\displaystyle \sum _{I\subseteq J}(-1)^{|J|-|I|}|A_{J}|.}$

Определите наборы

${\displaystyle B_{k}=A_{I\cup \{k\}}{\text{ for }}k\in N\setminus I.}$

Мы не ищем количество элементов ни в одном из B_k которые по принципу включения – исключения (с ${\displaystyle B_{\emptyset }=A_{I}}$), является

${\displaystyle \sum _{K\subseteq N\setminus I}(-1)^{|K|}|B_{K}|.}$

Переписка K ↔ J = я ∪ K между подмножествами N \ я и подмножества N содержащий я биекция и если J и K соответствуют под этой картой, тогда B_K = А_J, показывая, что результат верен.

По вероятности

В вероятность, для мероприятий А₁, ..., А_п в вероятностное пространство ${\displaystyle \scriptstyle (\Omega ,{\mathcal {F}},\mathbb {P} )}$, принцип включения – исключения становится для п = 2

${\displaystyle \mathbb {P} (A_{1}\cup A_{2})=\mathbb {P} (A_{1})+\mathbb {P} (A_{2})-\mathbb {P} (A_{1}\cap A_{2}),}$

за п = 3

${\displaystyle \mathbb {P} (A_{1}\cup A_{2}\cup A_{3})=\mathbb {P} (A_{1})+\mathbb {P} (A_{2})+\mathbb {P} (A_{3})-\mathbb {P} (A_{1}\cap A_{2})-\mathbb {P} (A_{1}\cap A_{3})-\mathbb {P} (A_{2}\cap A_{3})+\mathbb {P} (A_{1}\cap A_{2}\cap A_{3})}$

и вообще

${\displaystyle \mathbb {P} \left(\bigcup _{i=1}^{n}A_{i}\right)=\sum _{i=1}^{n}\mathbb {P} (A_{i})-\sum _{i<j}\mathbb {P} (A_{i}\cap A_{j})+\sum _{i<j<k}\mathbb {P} (A_{i}\cap A_{j}\cap A_{k})+\cdots +(-1)^{n-1}\sum _{i<...<n}\mathbb {P} \left(\bigcap _{i=1}^{n}A_{i}\right),}$

который в закрытом виде можно записать как

${\displaystyle \mathbb {P} \left(\bigcup _{i=1}^{n}A_{i}\right)=\sum _{k=1}^{n}\left((-1)^{k-1}\sum _{I\subseteq \{1,\ldots ,n\} \atop |I|=k}\mathbb {P} (A_{I})\right),}$

где последняя сумма проходит по всем подмножествам я индексов 1, ..., п которые содержат ровно k элементы и

${\displaystyle A_{I}:=\bigcap _{i\in I}A_{i}}$

обозначает пересечение всех этих А_я с индексом в я.

Согласно Неравенства Бонферрони, сумма первых членов в формуле попеременно является верхней и нижней оценкой для LHS. Это можно использовать в случаях, когда полная формула слишком громоздка.

Для генерала измерить пространство (S, Σ,μ) и измеримый подмножества А₁, ..., А_п конечной меры указанные выше тождества верны и при вероятностной мере ${\displaystyle \mathbb {P} }$ заменяется мерой μ.

Особый случай

Если в вероятностной версии принципа включения-исключения вероятность пересечения А_я зависит только от мощности я, что означает, что для каждого k в 1, ...,п} существует а_k такой, что

${\displaystyle a_{k}=\mathbb {P} (A_{I}){\text{ for every }}I\subset \{1,\ldots ,n\}{\text{ with }}|I|=k,}$

то приведенная выше формула упрощается до

${\displaystyle \mathbb {P} \left(\bigcup _{i=1}^{n}A_{i}\right)=\sum _{k=1}^{n}(-1)^{k-1}{\binom {n}{k}}a_{k}}$

благодаря комбинаторной интерпретации биномиальный коэффициент ${\displaystyle \scriptstyle {\binom {n}{k}}}$. Например, если события ${\displaystyle A_{i}}$ находятся независимые и одинаково распределенные, тогда ${\displaystyle \mathbb {P} (A_{i})=p}$ для всех я, и у нас есть ${\displaystyle a_{k}=p^{k}}$, и в этом случае выражение выше упрощается до

${\displaystyle \mathbb {P} \left(\bigcup _{i=1}^{n}A_{i}\right)=1-(1-p)^{n}.}$

(Этот результат также можно получить более просто, рассматривая пересечение дополнений событий ${\displaystyle A_{i}}$.)

Аналогичное упрощение возможно и в случае общего пространства с мерой (S, Σ,μ) и измеримые подмножества А₁, ..., А_п конечной меры.

Другие формы

Иногда принцип выражается в форме^[10] это говорит, что если

${\displaystyle g(A)=\sum _{S\subseteq A}f(S)}$

тогда

${\displaystyle f(A)=\sum _{S\subseteq A}(-1)^{|A|-|S|}g(S)\qquad (**)}$

Комбинаторная и вероятностная версии принципа включения-исключения являются примерами (**).

Доказательство

Брать ${\displaystyle {\underline {m}}=\{1,2,\ldots ,m\}}$, ${\displaystyle f({\underline {m}})=0}$, и ${\displaystyle f(S)=\left|\bigcap _{i\in {\underline {m}}\setminus S}A_{i}\setminus \bigcup _{i\in S}A_{i}\right|{\text{ and }}f(S)=\mathbb {P} \left(\bigcap _{i\in {\underline {m}}\setminus S}A_{i}\setminus \bigcup _{i\in S}A_{i}\right)}$ соответственно для всех наборы ${\displaystyle S}$ с ${\displaystyle S\subsetneq {\underline {m}}}$. Тогда получаем ${\displaystyle g(A)=\left|\bigcap _{i\in {\underline {m}}\setminus A}A_{i}\right|,\quad g({\underline {m}})=\left|\bigcup _{i\in {\underline {m}}}A_{i}\right|{\text{ and }}g(A)=\mathbb {P} \left(\bigcap _{i\in {\underline {m}}\setminus A}A_{i}\right),~~g({\underline {m}})=\mathbb {P} \left(\bigcup _{i\in {\underline {m}}}A_{i}\right)}$ соответственно для всех наборов ${\displaystyle A}$ с ${\displaystyle A\subsetneq {\underline {m}}}$. Это потому что элементы ${\displaystyle a}$ из ${\displaystyle \cap _{i\in {\underline {m}}\setminus A}A_{i}}$ возможно содержал в другом ${\displaystyle A_{i}}$ (${\displaystyle A_{i}}$ с ${\displaystyle i\in A}$), а ${\displaystyle \cap \setminus \cup \!{\text{-}}}$формула проходит через все возможные расширения множеств ${\displaystyle \{A_{i}\mid i\in {\underline {m}}\setminus A\}}$ с другим ${\displaystyle A_{i}}$, считая ${\displaystyle a}$ только для набора, который соответствует поведению членства ${\displaystyle a}$, если ${\displaystyle S}$ проходит через все подмножества из ${\displaystyle A}$ (как в определении ${\displaystyle g(A)}$). С ${\displaystyle f({\underline {m}})=0}$, получаем из (**) с ${\displaystyle A={\underline {m}}}$ который ${\displaystyle \sum _{{\underline {m}}\supseteq T\supsetneq \varnothing }(-1)^{|T|-1}g({\underline {m}}\setminus T)=\sum _{\varnothing \subseteq S\subsetneq {\underline {m}}}(-1)^{m-|S|-1}g(S)=g({\underline {m}})}$ а, поменяв местами стороны, следуют комбинаторная и вероятностная версии принципа включения-исключения.

Если вы видите число ${\displaystyle n}$ как набор его простых множителей, то (**) является обобщением Формула обращения Мебиуса за без квадратов натуральные числа. Следовательно, (**) рассматривается как формула обращения Мёбиуса для алгебра инцидентности из частично заказанный набор всех подмножеств А.

Для обобщения полной версии формулы обращения Мёбиуса, (**) необходимо обобщить на мультимножества. Для мультимножеств вместо наборов (**) становится

${\displaystyle f(A)=\sum _{S\subseteq A}\mu (A-S)g(S)\qquad (***)}$

куда ${\displaystyle A-S}$ это мультимножество, для которого ${\displaystyle (A-S)\uplus S=A}$, и

• μ(S) = 1, если S является набором (т.е. мультимножеством без двойных элементов) четное мощность.
• μ(S) = −1, если S - это множество (то есть мультимножество без двойных элементов) нечетной мощности.
• μ(S) = 0, если S является собственным мультимножеством (т.е. S имеет двойные элементы).

Заметь ${\displaystyle \mu (A-S)}$ это просто ${\displaystyle (-1)^{|A|-|S|}}$ из (**) в случае ${\displaystyle A-S}$ это набор.

Доказательство чего-либо (***)

Заменять ${\displaystyle g(S)=\sum _{T\subseteq S}f(T)}$ в правой части (***). Заметь ${\displaystyle f(A)}$ появляется один раз с обеих сторон (***). Итак, мы должны показать это всем ${\displaystyle T}$ с ${\displaystyle T\subsetneq A}$, условия ${\displaystyle f(T)}$ отменить в правой части (***). Для этого возьмите фиксированный ${\displaystyle T}$ такой, что ${\displaystyle T\subsetneq A}$ и возьмем произвольную фиксированную ${\displaystyle a\in A}$ такой, что ${\displaystyle a\not \in T}$. Заметь ${\displaystyle A-S}$ должен быть набор для каждого положительный или же отрицательный появление ${\displaystyle f(T)}$ в правой части (***), полученной с помощью мультимножества ${\displaystyle S}$ такой, что ${\displaystyle T\subseteq S\subseteq A}$. Теперь каждое появление ${\displaystyle f(T)}$ в правой части (***), которое получается с помощью ${\displaystyle S}$ такой, что ${\displaystyle A-S}$ это набор, содержащий ${\displaystyle a}$ отменяется тем, что получается посредством соответствующего ${\displaystyle S}$ такой, что ${\displaystyle A-S}$ это набор, не содержащий ${\displaystyle a}$. Это дает желаемый результат.

Приложения

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

Подсчет расстройств

Основная статья: Психическое расстройство

Хорошо известное приложение принципа включения-исключения - это комбинаторная задача подсчета всех расстройства конечного множества. А психическое расстройство набора А это биекция из А в себя, не имеющее фиксированных точек. С помощью принципа включения-исключения можно показать, что если мощность А является п, то количество неисправностей [п! / е] куда [Икс] обозначает ближайшее целое число к Икс; доступно подробное доказательство здесь а также увидеть раздел примеров над.

Впервые проблема подсчета количества расстройств встречается в одной из первых книг по азартным играм: Essai d'analyse sur les jeux de hazas П. Р. де Монморта (1678 - 1719) и была известна либо как «проблема Монморта», либо по названию, которое он дал ей ».проблема отношений."^[11] Проблема также известна как проблема с топором.

Количество расстройств также известно как субфакторный из п, написано!п. Отсюда следует, что если всем биекциям присвоена одинаковая вероятность, то вероятность того, что случайная биекция является расстройством, быстро приближается к 1 /е в качестве п растет.

Подсчет перекрестков

Принцип включения-исключения в сочетании с Закон де Моргана, можно также использовать для подсчета мощности пересечения множеств. Позволять ${\displaystyle {\overline {A_{k}}}}$ представляют собой дополнение А_k относительно некоторого универсального множества А такой, что ${\displaystyle A_{k}\subseteq A}$ для каждого k. Тогда у нас есть

${\displaystyle \bigcap _{i=1}^{n}A_{i}={\overline {\bigcup _{i=1}^{n}{\overline {A_{i}}}}}}$

тем самым превратив проблему поиска пересечения в проблему поиска союза.

Раскраска графика

Принцип исключения включения составляет основу алгоритмов для ряда NP-трудных задач разбиения графа, таких как раскраска графа.^[12]

Хорошо известным применением этого принципа является построение хроматический полином графа.^[13]

Идеальные соответствия двудольного графа

Количество идеальное соответствие из двудольный граф можно рассчитать по принципу.^[14]

Количество на функции

Учитывая конечные множества А и B, Как много сюръективные функции (на функции) есть от А к B? Без потери общности мы можем взять А = {1, ..., k} и B = {1, ..., п}, поскольку значение имеют только мощности множеств. Используя S как набор всех функции из А к B, и определяя для каждого я в B, недвижимость п_я поскольку "функция пропускает элемент я в B" (я не в изображение функции) принцип включения-исключения дает количество функций между А и B в качестве:^[15]

${\displaystyle \sum _{j=0}^{n}{\binom {n}{j}}(-1)^{j}(n-j)^{k}.}$

Перестановки с запрещенными позициями

А перестановка из набора S = {1, ..., п} где каждый элемент S ограничен тем, чтобы не находиться в определенных положениях (здесь перестановка рассматривается как упорядочение элементов S) называется перестановка с запрещенными позициями. Например, с S = {1,2,3,4}, перестановки с ограничением, что элемент 1 не может находиться в позициях 1 или 3, а элемент 2 не может находиться в позиции 4, следующие: 2134, 2143, 3124, 4123, 2341 , 2431, 3241, 3421, 4231 и 4321. Разрешая А_я набор позиций, которые элемент я запрещено находиться, а собственность п_я быть свойством, которым перестановка помещает элемент я в положение в А_я, принцип включения-исключения можно использовать для подсчета количества перестановок, удовлетворяющих всем ограничениям.^[16]

В данном примере 12 = 2 (3!) Перестановки со свойством п₁, 6 = 3! перестановки с собственностью п₂ и никакие перестановки не имеют свойств п₃ или же п₄ поскольку для этих двух элементов нет ограничений. Таким образом, количество перестановок, удовлетворяющих ограничениям, составляет:

4! − (12 + 6 + 0 + 0) + (4) = 24 − 18 + 4 = 10.

Последние 4 в этом вычислении - это количество перестановок, имеющих оба свойства п₁ и п₂. Других ненулевых вкладов в формулу нет.

Числа Стирлинга второго рода

Основная статья: Числа Стирлинга второго рода

В Числа Стирлинга второго рода, S(п,k) подсчитайте количество перегородки набора п элементы в k непустые подмножества (неразличимые коробки). Явную формулу для них можно получить, применив принцип включения-исключения к очень близкой задаче, а именно, подсчету числа разбиений п-установить в k непустые, но различимые коробки (упорядоченный непустые подмножества). Используя универсальный набор, состоящий из всех перегородок п-установить в k (возможно, пустые) различимые коробки, А₁, А₂, ..., А_k, а свойства п_я означает, что в разделе есть коробка А_я пустой, принцип включения – исключения дает ответ на связанный результат. Деление на k! для удаления искусственного упорядочения дает число Стирлинга второго вида:^[17]

${\displaystyle S(n,k)={\frac {1}{k!}}\sum _{t=0}^{k}(-1)^{t}{\binom {k}{t}}(k-t)^{n}.}$

Полиномы ладьи

Основная статья: Полином ладьи

Ладейный многочлен - это производящая функция из количества способов разместить не атакующие грачи на доска B это выглядит как подмножество квадратов шахматная доска; то есть две ладьи не могут находиться в одном ряду или столбце. Доска B любое подмножество квадратов прямоугольной доски с п ряды и м колонны; мы думаем об этом как о клетках, в которые разрешено ставить ладью. В коэффициент, р_k(B) из Икс^k в ладейном полиноме р_B(Икс) - количество способов k ладьи, ни одна из которых не атакует другую, могут быть расположены в квадратах B. Для любой доски B, есть дополнительная доска ${\displaystyle B'}$ состоящий из квадратов прямоугольной доски, не входящих в B. На этой дополнительной доске также есть ладейный многочлен ${\displaystyle R_{B'}(x)}$ с коэффициентами ${\displaystyle r_{k}(B').}$

Иногда бывает удобно вычислить наивысший коэффициент ладейного многочлена через коэффициенты ладейного многочлена дополнительной доски. Без ограничения общности можно считать, что п ≤ м, поэтому этот коэффициент равен р_п(B). Количество способов размещения п не атакующие ладьи по комплекту п × м «шахматная доска» (независимо от того, расположены ли ладьи в клетках доски) B) дается падающий факториал:

${\displaystyle (m)_{n}=m(m-1)(m-2)\cdots (m-n+1).}$

Сдача п_я быть собственностью, присвоенной п у не атакующих ладей на всей доске ладья в колонне я который не находится в квадрате доски B, то по принципу включения – исключения имеем:^[18]

${\displaystyle r_{n}(B)=\sum _{t=0}^{n}(-1)^{t}(m-t)_{n-t}r_{t}(B').}$

Функция фи Эйлера

Основная статья: Функция Эйлера

Функция Эйлера или функция фи, φ(п) является арифметическая функция который считает количество положительных целых чисел, меньших или равных п которые относительно простой к п. То есть, если п это положительное число, то φ (п) - количество целых чисел k в диапазоне 1 ≤ k ≤ п которые не имеют общего с п кроме 1. Принцип включения – исключения используется для получения формулы для φ (п). Позволять S - множество {1, ..., п} и определите свойство п_я быть тем числом в S делится на простое число п_я, для 1 ≤ я ≤ р, где простые множители из

${\displaystyle n=p_{1}^{a_{1}}p_{2}^{a_{2}}\cdots p_{r}^{a_{r}}.}$

Потом,^[19]

${\displaystyle \varphi (n)=n-\sum _{i=1}^{r}{\frac {n}{p_{i}}}+\sum _{1\leqslant i<j\leqslant r}{\frac {n}{p_{i}p_{j}}}-\cdots =n\prod _{i=1}^{r}\left(1-{\frac {1}{p_{i}}}\right).}$

Разбавленный принцип включения-исключения

Смотрите также: Неравенства Бонферрони

Во многих случаях, когда принцип может дать точную формулу (в частности, подсчет простые числа с использованием сито Эратосфена ) возникающая формула не предлагает полезного содержания, поскольку количество терминов в ней чрезмерно. Если каждый член в отдельности можно оценить точно, накопление ошибок может означать, что формула включения-исключения не применима напрямую. В теория чисел, эта проблема была решена Вигго Брун. После медленного старта его идеи были подхвачены другими, и многие ситовые методы развитый. Они, например, могут попытаться найти верхние границы для "просеянных" множеств, а не точную формулу.

Позволять А₁, ..., А_п быть произвольными множествами и п₁, ..., п_п действительные числа в замкнутом единичном интервале [0,1]. Тогда для каждого четного числа k в {0, ..., п}, индикаторные функции удовлетворяют неравенству:^[20]

${\displaystyle 1_{A_{1}\cup \cdots \cup A_{n}}\geq \sum _{j=1}^{k}(-1)^{j-1}\sum _{1\leq i_{1}<\cdots <i_{j}\leq n}p_{i_{1}}\dots p_{i_{j}}\,1_{A_{i_{1}}\cap \cdots \cap A_{i_{j}}}.}$

Доказательство основного утверждения

Выберите элемент, содержащийся в объединении всех наборов, и пусть ${\displaystyle A_{1},A_{2},\dots ,A_{t}}$ быть отдельными наборами, содержащими его. (Обратите внимание, что т > 0.) Поскольку элемент учитывается ровно один раз в левой части уравнения (1), нам нужно показать, что он учитывается в правой части ровно один раз. В правой части единственные ненулевые вклады происходят, когда все подмножества в конкретном члене содержат выбранный элемент, то есть все подмножества выбираются из ${\displaystyle A_{1},A_{2},\dots ,A_{t}}$. Вклад равен одному для каждого из этих наборов (плюс или минус в зависимости от термина) и, следовательно, представляет собой просто (подписанное) количество этих подмножеств, используемых в термине. Тогда у нас есть:

${\displaystyle {\begin{aligned}|\{A_{i}\mid 1\leqslant i\leqslant t\}|&-|\{A_{i}\cap A_{j}\mid 1\leqslant i<j\leqslant t\}|+\cdots +(-1)^{t+1}|\{A_{1}\cap A_{2}\cap \cdots \cap A_{t}\}|={\binom {t}{1}}-{\binom {t}{2}}+\cdots +(-1)^{t+1}{\binom {t}{t}}.\end{aligned}}}$

Посредством биномиальная теорема,

${\displaystyle 0=(1-1)^{t}={\binom {t}{0}}-{\binom {t}{1}}+{\binom {t}{2}}-\cdots +(-1)^{t}{\binom {t}{t}}.}$

Используя тот факт, что ${\displaystyle {\binom {t}{0}}=1}$ и переставляя сроки, мы имеем

${\displaystyle 1={\binom {t}{1}}-{\binom {t}{2}}+\cdots +(-1)^{t+1}{\binom {t}{t}},}$

и поэтому выбранный элемент засчитывается только один раз правой частью уравнения (1).

Алгебраическое доказательство

Алгебраическое доказательство можно получить, используя индикаторные функции (также называемые характеристическими функциями). Индикаторная функция подмножества S набора Икс это функция

${\displaystyle {\begin{cases}\mathbf {1} _{S}:X\to \{0,1\}\\\mathbf {1} _{S}(x)={\begin{cases}1&x\in S\\0&x\notin S\end{cases}}\end{cases}}}$

Если ${\displaystyle A}$ и ${\displaystyle B}$ два подмножества ${\displaystyle X}$, тогда

${\displaystyle \mathbf {1} _{A}\cdot \mathbf {1} _{B}=\mathbf {1} _{A\cap B}.}$

Позволять А обозначают объединение ${\textstyle \bigcup _{i=1}^{n}A_{i}}$ наборов А₁, ..., А_п. Чтобы доказать принцип включения-исключения в целом, сначала проверим тождество

${\displaystyle \mathbf {1} _{A}=\sum _{k=1}^{n}(-1)^{k-1}\sum _{I\subset \{1,\ldots ,n\} \atop |I|=k}\mathbf {1} _{A_{I}}}$

(∗)

для индикаторных функций, где:

${\displaystyle A_{I}=\bigcap _{i\in I}A_{i}.}$

Следующая функция

${\displaystyle \left(\mathbf {1} _{A}-\mathbf {1} _{A_{1}}\right)\left(\mathbf {1} _{A}-\mathbf {1} _{A_{2}}\right)\cdots \left(\mathbf {1} _{A}-\mathbf {1} _{A_{n}}\right),}$

тождественно равен нулю, потому что: если Икс не в А, то все множители равны 0 - 0 = 0; а в противном случае, если Икс принадлежит некоторым А_м, то соответствующий м^th коэффициент равен 1 - 1 = 0. Разложив произведение в левой части, получаем уравнение (∗).

Чтобы доказать принцип включения-исключения для мощности множеств, просуммируйте уравнение (∗) по всем Икс в союзе А₁, ..., А_п. Чтобы получить версию, используемую в вероятности, возьмите ожидание в (∗). В целом, интегрировать уравнение (∗) относительноμ. Всегда используйте линейность в этих выводах.

Смотрите также

• Комбинаторные принципы
• Неравенство Буля
• Проблема ожерелья
• Формула Шуэтта – Несбитта
• Идентичность максимума-минимума

Примечания

1. Робертс и Тесман 2009, стр. 405
2. Мазур 2010, стр. 94
3. ван Линт и Уилсон 1992, стр. 77
4. ван Линт и Уилсон 1992, стр. 77
5. Стэнли 1986, стр. 64
6. Рота, Джан-Карло (1964), "Об основах комбинаторной теории I. Теория функций Мёбиуса", Zeitschrift für Wahrscheinlichkeitstheorie, 2: 340–368, Дои:10.1007 / BF00531932
7. Мазур 2010, стр. 83–4, 88
8. Бруальди 2010, стр. 167–8
9. Кэмерон 1994, стр. 78
10. Грэхем, Грёчель и Ловас, 1995 г., стр. 1049
11. ван Линт и Уилсон 1992, стр. 77-8
12. Бьёрклунд, Хусфельдт и Койвисто, 2009 г.
13. Валовой 2008, стр. 211–13
14. Валовой 2008, стр. 208–10
15. Мазур 2008, стр.84-5, 90 Ошибка harvnb: цель отсутствует: CITEREFMazur2008 (помощь)
16. Бруальди 2010, стр. 177–81
17. Бруальди 2010, стр. 282–7
18. Робертс и Тесман 2009, стр.419–20
19. ван Линт и Уилсон 1992, стр. 73
20. (Фернандес, Фрёлих и Алан Д. 1992, Предложение 12.6)

Рекомендации

• Allenby, R.B.J.T .; Сломсон, Алан (2010), Как считать: введение в комбинаторику, Дискретная математика и ее приложения (2-е изд.), CRC Press, стр. 51–60, ISBN  9781420082609
• Björklund, A .; Husfeldt, T .; Койвисто, М. (2009), "Разбиение множества посредством включения-исключения", SIAM Журнал по вычислениям, 39 (2): 546–563, Дои:10.1137/070683933
• Бруальди, Ричард А. (2010), Вводная комбинаторика (5-е изд.), Прентис-Холл, ISBN  9780136020400
• Кэмерон, Питер Дж. (1994), Комбинаторика: темы, методы, алгоритмы, Издательство Кембриджского университета, ISBN  0-521-45761-0
• Фернандес, Роберто; Фрёлих, Юрг; Алан Д., Сокал (1992), Случайные блуждания, критические явления и тривиальность в квантовой теории поля, Тексты и монографии по физике, Берлин: Springer-Verlag, стр. xviii + 444, ISBN  3-540-54358-9, МИСТЕР  1219313, Zbl  0761.60061
• Graham, R.L .; Грётшель, М.; Ловас, Л. (1995), Справочник комбинаторики (том-2), MIT Press - Северная Голландия, ISBN  9780262071710
• Гросс, Джонатан Л. (2008), Комбинаторные методы с компьютерными приложениями, Чепмен и Холл / CRC, ISBN  9781584887430
• «Принцип включения-исключения», Энциклопедия математики, EMS Press, 2001 [1994]
• Мазур, Дэвид Р. (2010), Комбинаторика: экскурсия, Математическая ассоциация Америки, ISBN  9780883857625
• Робертс, Фред С .; Тесман, Барри (2009), Прикладная комбинаторика (2-е изд.), CRC Press, ISBN  9781420099829
• Стэнли, Ричард П. (1986), Перечислительная комбинаторика, том I, Уодсворт и Брукс / Коул, ISBN  0534065465
• van Lint, J.H .; Уилсон, Р. (1992), Курс комбинаторики, Издательство Кембриджского университета, ISBN  0521422604

В эту статью включены материалы из принципа включения – исключения по PlanetMath, который находится под лицензией Лицензия Creative Commons Attribution / Share-Alike.