В комбинаторике , одном из разделов математики , принцип включения-исключения - это метод подсчета, который обобщает известный метод определения числа элементов в объединении двух конечных множеств ; символически выражается как
где A и B - два конечных множества и | S | указывает мощность множества S (которую можно рассматривать как количество элементов в множестве, если множество конечно ). Формула выражает тот факт, что сумма размеров двух наборов может быть слишком большой, поскольку некоторые элементы могут быть пересчитаны дважды. Элементы с двойным счетом - это элементы, находящиеся на пересечении двух наборов, и счет корректируется путем вычитания размера пересечения.
Принцип более ясно виден в случае трех наборов, которые для наборов A , B и C задаются выражением
Эту формулу можно проверить, посчитав, сколько раз каждая область на диаграмме Венна включается в правую часть формулы. В этом случае при удалении вкладов чрезмерно подсчитанных элементов количество элементов во взаимном пересечении трех наборов вычиталось слишком часто, поэтому их необходимо добавить обратно, чтобы получить правильную сумму.
Обобщение результатов этих примеров дает принцип включения – исключения. Чтобы найти мощность объединения n множеств:
- Включите мощности множеств.
- Исключаем мощности попарных пересечений.
- Включите мощности тройных пересечений.
- Исключите мощности четверных пересечений.
- Включите мощности пятикратных пересечений.
- Продолжайте, пока мощность n- кратного пересечения не будет включена (если n нечетно) или исключена ( n четно).
Название происходит от идеи, что принцип основан на чрезмерном включении , за которым следует компенсирующее исключение . Эта концепция приписывается Аврааму де Муавру (1718 г.); [1], но сначала он появляется в статье Даниэля да Силвы (1854 г.), [2], а затем в статье Дж. Дж. Сильвестра (1883 г.). [3] Иногда принцип упоминается как формула Да Силвы или Сильвестра из-за этих публикаций. Принцип является примером ситового метода широко используется в теории чисел и иногда упоминается как сита формулы , [4] , хотя Лежандр уже использовал аналогичное устройство в сите контекста в 1808 году.
Поскольку конечные вероятности вычисляются как отсчеты относительно мощности вероятностного пространства , формулы для принципа включения-исключения остаются в силе, когда мощности множеств заменяются конечными вероятностями. В более общем плане обе версии принципа можно объединить под общим зонтом теории меры .
В очень абстрактной постановке принцип включения-исключения может быть выражен как вычисление инверсии определенной матрицы. [5] Это обратное имеет особую структуру, что делает принцип чрезвычайно ценным методом в комбинаторике и смежных областях математики. Как сказал Джан-Карло Рота : [6]
«Одним из наиболее полезных принципов перечисления в дискретной вероятности и комбинаторной теории является знаменитый принцип включения-исключения. При умелом применении этот принцип дал решение многих комбинаторных проблем».
Заявление
В общем виде принцип включения-исключения утверждает, что для конечных множеств A 1 , ..., A n выполняется тождество
( 1 )
Это можно компактно записать как
или же
Другими словами, чтобы подсчитать количество элементов в конечном объединении конечных наборов, сначала просуммируйте мощности отдельных наборов, затем вычтите количество элементов, которые появляются по крайней мере в двух наборах, затем добавьте обратно количество элементов, которые появляются в как минимум три набора, затем вычтите количество элементов, которые появляются как минимум в четырех наборах, и так далее. Этот процесс всегда заканчивается, поскольку не может быть элементов, которые встречаются в большем количестве наборов в объединении. (Например, если не может быть элементов, которые появляются более чем в наборы; эквивалентно, не может быть никаких элементов, которые появляются хотя бы в наборы.)
В приложениях часто можно увидеть принцип, выраженный в дополнительной форме. То есть, если S - конечное универсальное множество, содержащее все A i, и пустьобозначим дополнение к A i в S , по законам Де Моргана имеем
В качестве другого варианта утверждения, пусть P 1 , ..., P n будет списком свойств, которые элементы множества S могут иметь или не иметь, тогда принцип включения-исключения обеспечивает способ вычисления количества элементов из S , не обладающих ни одним из свойств. Просто позвольте A i быть подмножеством элементов S, которые обладают свойством P i, и используйте принцип в его дополнительной форме. Этот вариант принадлежит Дж . Дж. Сильвестру . [1]
Обратите внимание, что если вы учитываете только первые m
Примеры
Подсчет целых чисел
В качестве простого примера использования принципа включения – исключения рассмотрим вопрос: [7]
- Сколько целых чисел в {1, ..., 100} не делятся на 2, 3 или 5?
Пусть S = {1, ..., 100} и P 1 свойство, что целое число делится на 2, P 2 свойство, что целое число делится на 3, и P 3 свойство, что целое число делится на 5. Пусть A i - подмножество S , элементы которого обладают свойством P i, которое мы получаем при элементарном подсчете: | A 1 | = 50, | A 2 | = 33 и | A 3 | = 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 , равно
Применять принцип включения – исключения,
Каждое значение представляет набор тасовок, имеющих по крайней мере p значений m 1 , ..., m p в правильной позиции. Обратите внимание, что количество перемешиваний с правильными значениями не менее p зависит только от p , а не от конкретных значений. Например, количество перемешиваний с 1-й, 3-й и 17-й картами в правильном положении совпадает с количеством перемешиваний с правильными позициями 2-й, 5-й и 13-й карт. Имеет значение только то, что из n карт 3 были выбраны в правильной позиции. Таким образом, естьравные члены в сумме p (см. комбинацию ).
- количество порядков, в которых p элементов находятся в правильном положении, что равно количеству способов упорядочения оставшихся n - p элементов, или ( n - p ) !. Таким образом, окончательно получаем:
Перестановка, при которой ни одна карта не находится в правильном положении, называется психическим расстройством . Принимая п ! чтобы быть общим числом перестановок, вероятность Q того, что случайное перемешивание приведет к расстройству, дается выражением
усечение до n + 1 членов разложения Тейлора числа e −1 . Таким образом, вероятность угадать порядок перетасованной колоды карт и ошибиться по поводу каждой карты составляет примерно e −1 или 37%.
Особый случай
Ситуация, представленная в приведенном выше примере психического расстройства, возникает достаточно часто, чтобы заслужить особого внимания. [8] А именно, когда размер множеств пересечений, фигурирующих в формулах для принципа включения-исключения, зависит только от количества множеств в пересечениях, а не от того, какие множества появляются. Более формально, если пересечение
имеет ту же мощность, скажем, α k = | A J | для любого k -элементного подмножества J из {1, ..., n }, то
Или, в дополнительной форме, где универсальное множество S имеет мощность α 0 ,
Обобщение
Дано семейство (допускается повторение) подмножеств A 1 , A 2 , ..., A n универсального множества S , принцип включения-исключения вычисляет количество элементов S ни в одном из этих подмножеств. Обобщение этой концепции позволило бы вычислить количество элементов S, которые появляются точно в некоторых фиксированных m этих множеств.
Пусть N = [ n ] = {1,2, ..., n }. Если мы определим, то принцип включения – исключения можно записать как, используя обозначения предыдущего раздела; количество элементов S, содержащихся ни в одном из A i, равно:
Если I является фиксированным подмножеством набора индексов N , то количество элементов, принадлежащих A i для всех i в I и ни для каких других значений, равно: [9]
Определите наборы
Мы ищем количество элементов ни в одном из B k, которые по принципу включения-исключения (с), является
Соответствие K ↔ J = I ∪ K между подмножествами N \ I и подмножествами N, содержащими I, является биекцией, и если J и K соответствуют при этом отображении, то B K = A J , показывая, что результат верен.
По вероятности
В вероятности для событий A 1 , ..., А п в вероятностном пространстве , принцип включения – исключения становится при n = 2
для n = 3
и вообще
который в закрытом виде можно записать как
где последняя сумма пробегает все подмножества I индексов 1, ..., n, которые содержат ровно k элементов, и
обозначает пересечение всех тех , A I с индексом в I .
Согласно неравенствам Бонферрони , сумма первых членов в формуле попеременно является верхней и нижней границей для LHS . Это можно использовать в тех случаях, когда полная формула слишком громоздка.
Для общего пространства с мерой ( S , Σ, μ ) и измеримых подмножеств A 1 , ..., A n конечной меры указанные выше тождества также выполняются, когда вероятностная меразаменяется мерой μ .
Особый случай
Если в вероятностной версии принципа включения-исключения, вероятность пересечения I зависит только от мощности I , а это означает , что для каждого к в {1, ..., п } есть к таким образом, что
тогда приведенная выше формула упрощается до
благодаря комбинаторной интерпретации биномиального коэффициента . Например, если событияявляются независимыми и одинаково распределенными , тодля всех я , и у нас есть, и в этом случае выражение выше упрощается до
(Этот результат также можно получить более просто, рассматривая пересечение дополнений событий .)
Аналогичное упрощение возможно в случае общего пространства с мерой ( S , Σ, μ ) и измеримых подмножеств A 1 , ..., A n конечной меры.
Другие формы
Иногда принцип выражается в форме [10], в которой говорится, что если
тогда
Комбинаторная и вероятностная версии принципа включения-исключения являются примерами (**).
Доказательство |
---|
Брать , , а также соответственно для всех наборов с участием . Тогда получаем соответственно для всех наборов с участием . Это потому, что элементы из может содержаться в других ( с участием ), а формула проходит через все возможные расширения множеств с прочими , считая только для набора, который соответствует поведению членства , если пробегает все подмножества из (как в определении ). С , получаем из (**) с что и, меняя местами стороны, следуют комбинаторная и вероятностная версии принципа включения-исключения. |
Если увидишь число как набор его простых множителей, то (**) является обобщением формулы обращения Мёбиуса для натуральных чисел без квадратов . Таким образом, (**) рассматриваются как формула обращения Мёбиуса для падения алгебры из частично упорядоченного множества всех подмножеств A .
Для обобщения полной версии формулы обращения Мёбиуса, (**) необходимо обобщить на мультимножества . Для мультимножеств вместо наборов (**) становится
где мультимножество, для которого , а также
- μ ( S ) = 1, если S - множество (т. е. мультимножество без двойных элементов) четной мощности .
- μ ( S ) = −1, если S - множество (т. е. мультимножество без двойных элементов) нечетной мощности.
- μ ( S ) = 0, если S - собственное мультимножество (т. е. S имеет двойные элементы).
Заметь это просто из (**) в случае это набор.
Доказательство чего-либо (***) |
---|
Заменять в правой части (***). Заметьпоявляется один раз с обеих сторон (***). Итак, мы должны показать это всем с участием , условия отменить в правой части (***). Для этого возьмите фиксированный такой, что и возьмем произвольную фиксированную такой, что . Заметь должен быть набором для каждого положительного или отрицательного появления в правой части (***), полученной с помощью мультимножества такой, что . Теперь каждое появление в правой части (***), которое получается с помощью такой, что это набор, содержащий отменяется тем, что получается посредством соответствующего такой, что это набор, не содержащий . Это дает желаемый результат. |
Приложения
Принцип включения-исключения широко используется, и здесь можно упомянуть лишь некоторые из его приложений.
Подсчет расстройств
Хорошо известное приложение принципа включения-исключения - это комбинаторная задача подсчета всех неисправностей конечного множества. Психоз из множества А является взаимно однозначным соответствием из A в себя , что имеет неподвижные точки. С помощью принципа включения-исключения можно показать, что если мощность A равна n , то количество неисправностей равно [ n ! / e ], где [ x ] обозначает ближайшее к x целое число ; подробное доказательство доступно здесь, а также см. раздел примеров выше.
Впервые проблема подсчета количества психических расстройств встречается в одной из первых книг об азартных играх: Essai d'analyse sur les jeux de risk, написанной П.Р. де Монмором (1678-1719) и известная как «проблема Монморта», либо как «проблема Монморта». по названию, которое он дал ей, « проблема общения ». [11] Проблема также известна как проблема топора.
Количество неисправностей также известно как субфактор от n , написано! п . Отсюда следует, что если всем биекциям присваивается одинаковая вероятность, то вероятность того, что случайная биекция является расстройством, быстро приближается к 1 / e с ростом n .
Подсчет перекрестков
Принцип включения-исключения в сочетании с законом Де Моргана также можно использовать для подсчета мощности пересечения множеств. Позволятьпредставляют собой дополнение A k относительно некоторого универсального множества A, такого чтодля каждого k . Тогда у нас есть
тем самым превращая проблему поиска пересечения в проблему поиска союза.
Раскраска графика
Принцип исключения включения составляет основу алгоритмов для ряда NP-трудных задач разбиения графа, таких как раскраска графа. [12]
Хорошо известное применение этого принципа - построение хроматического полинома графа. [13]
Идеальные соответствия двудольного графа
Количество совершенных паросочетаний одного двудольного графа может быть вычислено с использованием принципа. [14]
Количество на функции
Учитывая конечные множества A и B , сколько сюръективных функций (на функции) имеется от A до B ? Без потери общности мы можем взять A = {1, ..., k } и B = {1, ..., n }, поскольку имеют значение только мощности множеств. Используя S как набор всех функций от A до B и определяя для каждого i в B свойство P i как «функция пропускает элемент i в B » ( i отсутствует в изображении функции), принцип включения-исключения дает количество функций между A и B как: [15]
Перестановки с запрещенными позициями
Перестановки множество 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 , принцип включения-исключения может использоваться для подсчета количества перестановок, удовлетворяющих всем ограничениям. [16]
В данном примере 12 = 2 (3!) Перестановки со свойством P 1 , 6 = 3! перестановки со свойством P 2 и без перестановок обладают свойствами P 3 или P 4, поскольку для этих двух элементов нет ограничений. Таким образом, количество перестановок, удовлетворяющих ограничениям, составляет:
- 4! - (12 + 6 + 0 + 0) + (4) = 24 - 18 + 4 = 10.
Последние 4 в этом вычислении - это количество перестановок, обладающих как свойствами P 1, так и P 2 . Других ненулевых вкладов в формулу нет.
Числа Стирлинга второго рода
Эти числа Стирлинга второго рода , S ( п , K ) подсчитать количество перегородок из множества п элементов в к непустых подмножеств (неразличимые коробки ). Явная формула для них может быть получена путем применения принципа включения-исключения к очень тесно связанной задаче, а именно, подсчету числа разбиений n -множества на k непустых, но различимых ящиков ( упорядоченных непустых подмножеств) . Используя универсальный набор, состоящий из всех разбиений n -множества на k (возможно, пустых) различимых ящиков, A 1 , A 2 , ..., A k , и свойства P i, означающие, что в разделе есть пустое поле A i , принцип включения-исключения дает ответ на связанный результат. Делим на k ! для удаления искусственного упорядочения дает число Стирлинга второго рода: [17]
Полиномы ладьи
Полином ладьи - это производящая функция количества способов разместить не атакующие ладьи на доске B, которая выглядит как подмножество полей шахматной доски ; то есть две ладьи не могут находиться в одном ряду или столбце. Доска B - это любое подмножество квадратов прямоугольной доски с n строками и m столбцами; мы думаем об этом как о клетках, в которые разрешено ставить ладью. Коэффициент , т к ( В ) от х к в ладейной полинома R B ( х ) есть число способов K ладей, ни один из которых атакует другой, могут быть расположены на площадях B . Для любой доски B есть дополнительная доска.состоящие из квадратов прямоугольной доски, которые не являются в B . Эта дополнительная доска также имеет ладейный многочлен с коэффициентами
Иногда бывает удобно вычислить наивысший коэффициент ладейного многочлена через коэффициенты ладейного многочлена дополнительной доски. Без ограничения общности можно считать, что n ≤ m , поэтому этот коэффициент равен r n ( B ). Количество способов разместить n не атакующих ладей на полной «шахматной доске» n × m (независимо от того, находятся ли ладьи в клетках доски B ) определяется факториалом падения :
Пусть P i - это свойство, что при расстановке n не атакующих ладей на всей доске в столбце i находится ладья, которая не находится в квадрате доски B , тогда по принципу включения-исключения имеем: [18]
Функция фи Эйлера
Функция Эйлера, или функция фи, φ ( n ) - это арифметическая функция, которая подсчитывает количество положительных целых чисел, меньших или равных n , которые взаимно просты с n . То есть, если n - положительное целое число , то φ ( n ) - это количество целых чисел k в диапазоне 1 ≤ k ≤ n, которые не имеют общего делителя с n, кроме 1. Принцип включения-исключения используется для получения формула для φ ( n ). Пусть S - множество {1, ..., n }, и определим свойство P i как то, что число в S делится на простое число p i , для 1 ≤ i ≤ r , где разложение на простые множители числа
Тогда [19]
Разбавленный принцип включения-исключения
Во многих случаях, когда принцип может дать точную формулу (в частности, подсчет простых чисел с помощью сита Эратосфена ), возникающая формула не предлагает полезного содержания, потому что количество терминов в ней чрезмерно. Если каждый член в отдельности можно оценить точно, накопление ошибок может означать, что формула включения-исключения не применима напрямую. В теории чисел эту трудность рассмотрел Вигго Брун . После медленного старта его идеи были подхвачены другими, и было разработано большое количество методов сита . Они, например, могут попытаться найти верхние границы для "просеянных" множеств, а не точную формулу.
Пусть A 1 , ..., A n - произвольные множества и p 1 , ..., p n действительные числа в замкнутом единичном интервале [0,1]. Тогда для каждого четного числа k из {0, ..., n } индикаторные функции удовлетворяют неравенству: [20]
Доказательство основного утверждения
Выберите элемент, содержащийся в объединении всех наборов, и пусть быть отдельными наборами, содержащими его. (Обратите внимание, что t > 0.) Поскольку элемент учитывается ровно один раз в левой части уравнения ( 1 ), нам нужно показать, что он учитывается ровно один раз в правой части. С правой стороны, единственные ненулевые вклады происходят, когда все подмножества в конкретном члене содержат выбранный элемент, то есть все подмножества выбраны из. Вклад составляет один для каждого из этих наборов (плюс или минус в зависимости от термина) и, следовательно, представляет собой просто (подписанное) количество этих подмножеств, используемых в термине. Тогда у нас есть:
По бинома Ньютона ,
Используя тот факт, что и переставляя термины, мы имеем
Таким образом, выбранный элемент учитывается только один раз в правой части уравнения ( 1 ).
Алгебраическое доказательство
Алгебраическое доказательство может быть получено с помощью индикаторных функций (также известных как характеристические функции). Индикаторной функцией подмножества S множества X является функция
Если а также два подмножества , тогда
Обозначим через A объединениемножеств A 1 , ..., A n . Чтобы доказать принцип включения-исключения в целом, сначала проверим тождество
(*)
для индикаторных функций, где:
Следующая функция
тождественно равен нулю, потому что: если x не принадлежит A , то все множители равны 0 - 0 = 0; а в противном случае, если х действительно принадлежат к некоторым А м , то соответствующие м е коэффициента равны 1 - 1 = 0. За счетом расширения продукта на стороне левой руки, уравнение (*) следующим образом .
Чтобы доказать принцип включения-исключения для мощности множеств, просуммируйте уравнение (∗) по всем x в объединении A 1 , ..., A n . Чтобы получить версию, используемую в вероятности, возьмите математическое ожидание в (*). В общем, проинтегрируем уравнение (∗) по μ . Всегда используйте линейность в этих выводах.
Смотрите также
- Комбинаторные принципы
- Неравенство Буля
- Проблема с ожерельем
- Формула Шуэтта – Несбитта
- Идентичность максимума-минимума
Заметки
- ^ a b Робертс и Тесман 2009 , стр. 405
- ↑ Mazur 2010 , стр. 94
- ↑ van Lint & Wilson 1992 , pg. 77
- ↑ van Lint & Wilson 1992 , pg. 77
- ↑ Стэнли 1986 , стр. 64
- ^ Rota, Джан-Карло (1964), "Об основах combinatoial теории I. Теория функций Мёбиуса", Zeitschrift für Wahrscheinlichkeitstheorie , 2 : 340-368, DOI : 10.1007 / BF00531932
- ^ Мазур 2010 , стр. 83-4, 88
- ^ Бруальди 2010 , стр. 167-8
- ^ Кэмерон 1994 , стр. 78
- ^ Graham, Grötschel & Lovász 1995 , стр. 1049
- ^ Ван Линт & Wilson 1992 , стр. 77-8
- ^ Björklund, Husfeldt & Koivisto 2009
- ^ Gross 2008 , стр. 211-13
- ^ Gross 2008 , стр. 208-10
- ^ Мазур 2008 , pp.84-5, 90
- ^ Бруальди 2010 , стр. 177-81
- ^ Бруальди 2010 , стр. 282-7
- ^ Roberts & Tesman 2009 , pp.419-20
- ↑ van Lint & Wilson 1992 , pg. 73
- ^ ( Фернандес, Фрёлих и Алан Д. 1992 , Предложение 12.6)
Рекомендации
- Алленби, 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 .