Введение

Метод подсчета в комбинаторике

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

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

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

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

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

Приложения

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

Расстройства счета

Хорошо известное применение принципа включения и исключения связано с комбинаторной задачей подсчёта всех беспорядков конечного множества. Беспорядок множества A — это биекция из A в само себя, не имеющая неподвижных точек. С помощью принципа включения и исключения можно показать, что если кардинальность A равна n, то число беспорядков равно [n! / e], где [x] обозначает ближайшее целое число к x; подробное доказательство доступно здесь, а также см. раздел «Примеры» выше. Впервые задача подсчёта числа беспорядков появилась в ранней книге об играх случая: Essai d'analyse sur les jeux de hazard П. Р. де Монмора (1678–1719) и была известна как «проблема Монмора» или под названием, которое он ей дал, «problème des rencontres». Эта задача также известна как задача о проверке пальто. Число беспорядков также известно как субфакториал n и обозначается !n. Отсюда следует, что если всем биекциям присвоена одинаковая вероятность, то вероятность того, что случайная биекция является беспорядком, быстро стремится к 1/e при увеличении n.

Подсчет пересечений

Принцип включения и исключения, в сочетании с законом Де Моргана, может быть использован для подсчета мощности пересечения множеств. Пусть обозначает дополнение Ak относительно некоторого универсального множества A, такое что для каждого k. Тогда мы тем самым сводим задачу нахождения пересечения к задаче нахождения объединения.

Цвет графика

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

Идеальное совпадение двухчастичного графа

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

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

При заданных конечных множествах A и B, сколько существует сюръективных функций (отображений "на") из A в B? Без потери общности можно считать, что A = {1, …, k} и B = {1, …, n}, поскольку важны только мощности множеств. Обозначим через S множество всех функций из A в B и определим для каждого i из B свойство Pi как "функция не принимает значение i в B" (i не входит в образ функции). Тогда по принципу включения-исключения число отображений "на" из A в B равно:

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

Пермутация множества S = {1, …, n}, где каждый элемент S ограничен тем, что он не может находиться в определенных позициях (здесь пермутация рассматривается как упорядочение элементов S), называется пермутацией с запрещенными позициями. Например, при S = {1, 2, 3, 4}, перестановки с ограничением, что элемент 1 не может быть в позициях 1 или 3, а элемент 2 не может быть в позиции 4, следующие: 2134, 2143, 3124, 4123, 2341, 2431, 3241, 3421, 4231 и 4321. Пусть Ai будет множеством позиций, в которых элемент i не может находиться, а свойство Pi – свойством, при котором перестановка помещает элемент i в позицию из Ai. Принцип включения-исключения может быть использован для подсчета количества перестановок, удовлетворяющих всем ограничениям. В приведенном примере имеется 12 = 2 * (3!) перестановок со свойством P1, 6 = 3! перестановок со свойством P2, и нет перестановок, обладающих свойствами P3 или P4, поскольку для этих двух элементов нет ограничений. Таким образом, число перестановок, удовлетворяющих ограничениям, равно: 4! − (12 + 6 + 0 + 0) + (4) = 24 − 18 + 4 = 10. Последняя 4 в этом вычислении – это количество перестановок, обладающих обоими свойствами P1 и P2. Других ненулевых слагаемых в формуле нет.

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

Числа Стирлинга второго рода, S(n,k), подсчитывают количество разбиений множества из n элементов на k непустых подмножеств (неразличимых ящиков). Явную формулу для них можно получить, применив принцип включения-исключения к тесно связанной задаче, а именно, подсчету количества разбиений множества из n элементов на k непустых, но различимых ящиков (упорядоченных непустых подмножеств). Используя универсальное множество, состоящее из всех разбиений множества из n элементов на k (возможно пустых) различимых ящиков, A1, A2, ..., Ak, и свойства Pi, означающие, что в разбиении ящик Ai пуст, принцип включения-исключения дает решение для связанной задачи. Деление на k! для устранения искусственного упорядочения дает число Стирлинга второго рода.

Принцип разбавленного включения и исключения

Во многих случаях, когда принцип может дать точную формулу (в частности, при подсчете простых чисел с помощью решета Эратосфена), полученная формула не несет полезной информации, поскольку число слагаемых в ней чрезмерно велико. Если каждое слагаемое можно оценить достаточно точно по отдельности, накопление ошибок может означать, что формула включений и исключений неприменима напрямую. В теории чисел эту трудность исследовал Вигго Брун. После неспешного старта его идеи были подхвачены другими, и было разработано множество методов решета. Например, они могут стремиться найти верхние оценки для "просеянных" множеств, а не точную формулу. Пусть A1, ..., An – произвольные множества, а p1, ..., pn – действительные числа из замкнутого единичного интервала. Тогда для каждого четного числа k из множества {0, ..., n} индикаторные функции удовлетворяют следующему неравенству: