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

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

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

{ Displaystyle | A чашка B | = | A | + | B | - | A cap B |,}

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

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

{ Displaystyle | A чашка B чашка C | = | A | + | B | + | C | - | A cap B | - | A cap C | - | B cap C | + | A cap B cap C |.}

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

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

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

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

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

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

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

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

Заявление

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

{ displaystyle left | bigcup _ {i = 1} ^ {n} A_ {i} right | = sum _ {i = 1} ^ {n} | A_ {i} | - sum _ {1 leqslant i

(1)

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

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

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

или же

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

Другими словами, чтобы подсчитать количество элементов в конечном объединении конечных наборов, сначала просуммируйте мощности отдельных наборов, затем вычтите количество элементов, которые появляются по крайней мере в двух наборах, затем добавьте обратно количество элементов, которые появляются в как минимум три набора, затем вычтите количество элементов, которые появляются как минимум в четырех наборах, и так далее. Этот процесс всегда заканчивается, поскольку не может быть элементов, которые встречаются в большем количестве наборов в объединении. (Например, если ${ Displaystyle п = 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

В качестве другого варианта утверждения пусть $п 1, ..., п п$ быть списком свойств, которые элементы набора $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}

Каждое значение ${ 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 {align} W & = {n choose 1} (n-1)! - {n choose 2} (n-2)! + cdots + (- 1) ^ {p-1} {n choose p} (np)! + cdots & = sum _ {p = 1} ^ {n} (- 1) ^ {p-1} {n choose p} (np)! & = sum _ {p = 1} ^ {n} (- 1) ^ {p-1} { frac {n!} {p! (np)!}} (np)! & = сумма _ {p = 1} ^ {n} (- 1) ^ {p-1} { frac {n!} {p!}} end {выравнивается}}}

Перестановка, где нет карта в правильном положении называется психическое расстройство. Принимая п! быть общим числом перестановок, вероятность 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 А _ { emptyset} = S}$ , то принцип включения – исключения можно записать в виде, используя обозначения предыдущего раздела; количество элементов S не содержится ни в одном из А_я является:

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

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

{ displaystyle sum _ {I substeq 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 substeq 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} чашка A_ {2}) = mathbb {P} (A_ {1}) + mathbb {P} (A_ {2}) - mathbb {P} (A_ {1} cap A_ {2}),}

за п = 3

{ Displaystyle mathbb {P} (A_ {1} чашка A_ {2} чашка 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

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

{ displaystyle mathbb {P} left ( bigcup _ {i = 1} ^ {n} A_ {i} right) = sum _ {k = 1} ^ {n} left ((- 1) ^ {k-1} sum _ {I substeq {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 {для каждого}} 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 г (А) = сумма _ {S substeq A} е (S)}

тогда

{ Displaystyle е (A) = сумма _ {S substeq 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 {и}} 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 _ {я 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 substeq S subsetneq { underline {m}}} (- 1) ^ {m- | S | -1} g (S) = g ({ underline {m}})}

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

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

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

{ Displaystyle е (А) = сумма _ {S substeq A} му (A-S) г (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 г (S) = сумма _ {T substeq 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 substeq S substeq 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} substeq 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} } (kt) ^ {n}.}

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

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

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

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

Позволять А₁, ..., А_п быть произвольными множествами и п₁, ..., п_п действительные числа в замкнутом единичном интервале [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

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

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

{ displaystyle { begin {align} | {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 {выравнивается}} }

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

{ 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 {case}} end {case}}}

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

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

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

{ displaystyle mathbf {1} _ {A} = sum _ {k = 1} ^ {n} (- 1) ^ {k-1} sum _ {I subset {1, ldots, n } наверху | 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. Разложив произведение в левой части, получаем уравнение (∗).

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

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

Примечания

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

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

Содержание

Заявление

Примеры

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

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

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

Обобщение

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

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

Другие формы

Приложения

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

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

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

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

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

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

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

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

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

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

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

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

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

Примечания

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