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

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

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

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

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

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

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

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

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

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

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

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

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

Заявление

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

${\ 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 \ substeq \ {1, \ ldots, n \}} (- 1) ^ {| J | +1} \ left | \ bigcap _ {j \ in J} A_ {j} \ right |.}$

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

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

${\ 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} |.}$

В качестве другого варианта утверждения, пусть P ₁ , ..., P _n будет списком свойств, которые элементы множества S могут иметь или не иметь, тогда принцип включения-исключения обеспечивает способ вычисления количества элементов из S , не обладающих ни одним из свойств. Просто позвольте A _i быть подмножеством элементов S, которые обладают свойством P _i, и используйте принцип в его дополнительной форме. Этот вариант принадлежит Дж . Дж. Сильвестру .

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

Примеры

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

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

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

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

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

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

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

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

Начните с определения набора A _m , который представляет собой все правильные порядки карт с m- й картой. Тогда количество заказов W , по крайней мере , с одной картой, находящейся в правильном положении, m , равно

${\ 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}$

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

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

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

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

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

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

${\ 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}.}$

Обобщение

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

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

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

Если I является фиксированным подмножеством набора индексов N , то количество элементов, принадлежащих A _i для всех i в I и ни для каких других значений, равно:

${\ 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 = I ∪ K между подмножествами N  \  I и подмножествами N, содержащими I, является биекцией, и если J и K соответствуют при этом отображении, то B _K = A _J , показывая, что результат верен.

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

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

${\ Displaystyle \ mathbb {P} (A_ {1} \ чашка A_ {2}) = \ mathbb {P} (A_ {1}) + \ mathbb {P} (A_ {2}) - \ mathbb {P} (A_ {1} \ cap A_ {2}),}$

для n  = 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 <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 \ substeq \ {1, \ ldots, n \} \ atop | I | = k} \ mathbb {P} (A_ {I}) \ right),}$

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

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

обозначает пересечение всех тех , A _I с индексом в I .

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

Для общего пространства с мерой ( S , Σ, μ ) и измеримых подмножеств A ₁ , ..., A _n конечной меры указанные выше тождества также выполняются, когда вероятностная мера заменяется мерой μ . ${\ Displaystyle \ mathbb {P}}$

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

Если в вероятностной версии принципа включения-исключения, вероятность пересечения _I зависит только от мощности I , а это означает , что для каждого к в {1, ...,  п } есть _к таким образом, что

${\ 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}}$

благодаря комбинаторной интерпретации биномиального коэффициента . Например, если события являются независимыми и одинаково распределенными , то для всех I , и у нас есть , в этом случае приведенное выше выражение упрощается ${\ 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 , Σ, μ ) и измеримых подмножеств A ₁ , ..., A _n конечной меры.

Другие формы

Иногда принцип выражается в форме, которая гласит, что если

${\ Displaystyle г (А) = \ сумма _ {S \ substeq A} е (S)}$

тогда

${\ Displaystyle е (A) = \ сумма _ {S \ substeq A} (- 1) ^ {| A | - | S |} g (S) \ qquad (**)}$

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

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

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

${\ Displaystyle е (А) = \ сумма _ {S \ substeq A} \ му (AS) г (S) \ qquad (***)}$

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

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

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

Приложения

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

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

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

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

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

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

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

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

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

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

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

Хорошо известное применение этого принципа - построение хроматического полинома графа.

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

Количество совершенных паросочетаний одного двудольного графа может быть вычислено с использованием принципа.

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

Учитывая конечные множества A и B , сколько сюръективных функций (на функции) имеется от A до B ? Без потери общности мы можем взять A = {1, ..., k } и B = {1, ..., n }, поскольку имеют значение только мощности множеств. Используя S как набор всех функций от A до B и определяя для каждого i в B свойство P _i как «функция пропускает элемент i в B » ( i отсутствует в изображении функции), принцип включения-исключения дает количество функций между A и B как:

${\ displaystyle \ sum _ {j = 0} ^ {n} {\ binom {n} {j}} (- 1) ^ {j} (nj) ^ {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. Допустим, что A _i будет набором позиций, в которых элемент i не может находиться, а свойство P _i будет свойством, которое перестановка помещает элемент i в позицию в A _i , принцип включения-исключения может использоваться для подсчета количества перестановок, удовлетворяющих всем ограничениям.

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

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

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

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

Эти числа Стирлинга второго рода , S ( п , K ) подсчитать количество перегородок из множества п элементов в к непустых подмножеств (неразличимые коробки ). Явная формула для них может быть получена путем применения принципа включения-исключения к очень тесно связанной задаче, а именно, подсчету числа разбиений n -множества на k непустых, но различимых ящиков ( упорядоченных непустых подмножеств) . Используя универсальный набор, состоящий из всех разбиений n -множества на k (возможно, пустых) различимых ящиков, A ₁ , A ₂ , ..., A _k , и свойства P _i, означающие, что в разделе есть пустое поле A _i , принцип включения-исключения дает ответ на связанный результат. Делим на k ! для удаления искусственного упорядочения дает число Стирлинга второго рода:

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

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

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

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

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

Пусть P _i - это свойство, что при расстановке n не атакующих ладей на всей доске в столбце i находится ладья, которая не находится в квадрате доски B , тогда по принципу включения-исключения имеем:

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

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

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

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

Потом,

${\ 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 }}}\Правильно).}$

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

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

Пусть A ₁ , ..., A _n - произвольные множества и p ₁ , ..., p _n действительные числа в замкнутом единичном интервале [0,1]. Тогда для каждого четного числа k из {0, ..., n } индикаторные функции удовлетворяют неравенству:

${\ 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}}}.}$

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

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

${\ 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}.}$

Обозначим через A объединение множеств A ₁ , ..., A _n . Чтобы доказать принцип включения-исключения в целом, сначала проверим тождество ${\ 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),}$

тождественно равен нулю, потому что: если x не принадлежит A , то все множители равны 0 - 0 = 0; а в противном случае, если х действительно принадлежат к некоторым А _м , то соответствующие м ^е коэффициента равны 1 - 1 = 0. За счетом расширения продукта на стороне левой руки, уравнение (*) следующим образом .

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

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

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

Примечания

использованная литература

• Алленби, RBJT; Сломсон, Алан (2010), Как считать : Введение в комбинаторику , дискретную математику и ее приложения (2-е изд.), CRC Press, стр. 51–60, ISBN 9781420082609
• Björklund, A .; Husfeldt, T .; Коивисто, М. (2009), "Установить разделение с помощью включения-исключения", SIAM журнал по вычислениям , 39 (2): 546-563, DOI : 10,1137 / 070683933
• Бруальди, Ричард А. (2010), Вводная комбинаторика (5-е изд.), Прентис-Холл, ISBN 9780136020400
• Кэмерон, Питер Дж. (1994), Комбинаторика: темы, методы, алгоритмы , Cambridge University Press, ISBN 0-521-45761-0
• Фернандес, Роберто; Fröhlich, Jürg ; Алан Д., Сокал (1992), Случайные блуждания, критические явления и тривиальность в квантовой теории поля , Тексты и монографии по физике, Берлин: Springer-Verlag , стр. Xviii + 444, ISBN 3-540-54358-9, Руководство по ремонту  1219313 , Zbl  0761.60061
• Graham, RL; Grötschel, M .; Ловас, Л. (1995), Справочник по комбинаторике (том-2) , MIT Press - Северная Голландия, ISBN 9780262071710
• Гросс, Джонатан Л. (2008), Комбинаторные методы с компьютерными приложениями , Chapman & Hall / CRC, ISBN 9781584887430
• «Принцип включения-исключения» , Энциклопедия математики , EMS Press , 2001 [1994]
• Мазур, Дэвид Р. (2010), Экскурсия по комбинаторике , Математическая ассоциация Америки, ISBN 9780883857625
• Робертс, Фред С .; Тесман, Барри (2009), Прикладная комбинаторика (2-е изд.), CRC Press, ISBN 9781420099829
• Стэнли, Ричард П. (1986), том I перечислительной комбинаторики , Wadsworth & Brooks / Cole, ISBN 0534065465
• ван Линт, JH; Уилсон, RM (1992), курс комбинаторики , Cambridge University Press, ISBN 0521422604

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