Основные положения включений и исключений на примере решения задач

Простая задачка о перестановках Сколько есть перестановок чисел от до таких, что первый элемент больше, а последний — меньше 8?

Посчитаем число «плохих» перестановок, т. е. таких, у которых первый элемент и/или последний .

Обозначим через X множество перестановок, у которых первый элемент, а через Y — у которых последний элемент. Тогда количество «плохих» перестановок по формуле включений-исключений равно:

Проведя несложные комбинаторные вычисления, получаем, что это равно:

Отнимая это число от общего числа перестановок, мы получим ответ.

Простая задачка о (0,1,2)-последовательностях Сколько существует последовательностей длины, состоящих только из чисел 0, 1, 2, причём каждое число встречается хотя бы раз?

Снова перейдём к обратной задаче, т. е. будем считать число последовательностей, в которых не присутствует хотя бы одно из чисел.

Обозначим через Ai.(i=0…2) множество последовательностей, в которых не встречается число i Тогда по формуле включений-исключений число «плохих» последовательностей равно:

Размеры каждого из Ai равны, очевидно, 2n (поскольку в таких последовательностях могут встречаться только два вида цифр). Мощности каждого попарного пересечения равны (поскольку остаётся доступной только одна цифра). Наконец, мощность пересечения всех трёх множеств равна (поскольку доступных цифр вообще не остаётся).

Вспоминая, что мы решали обратную задачу, получаем итоговый ответ:

Количество целочисленных решений уравнения Дано уравнение:

x1+x2+x3+x4+x5+x6=20.

где все (где).

Требуется посчитать число решений этого уравнения.

Забудем сначала про ограничение, и просто посчитаем число неотрицательных решений этого уравнения. Это легко делается через биномиальные коэффициенты — мы хотим разбить элементов на групп, т. е. распределить «стенок», разделяющих группы, по местам:

Посчитаем теперь по формуле включений-исключений число «плохих» решений, т. е. таких решений уравнения, в которых один или более больше. Обозначим через (где) множество таких решений уравнения, в которых, а все остальные (для всех). Чтобы посчитать размер множества, заметим, что у нас по сути та же комбинаторная задача, что решалась двумя абзацами выше, только теперь элементов исключены из рассмотрения и точно принадлежат первой группе. Таким образом:

Аналогично, мощность пересечения двух множеств и равна числу:

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

Объединяя всё это в формулу включений-исключений и учитывая, что мы решали обратную задачу, окончательно получаем ответ:

Количество взаимно простых чисел в заданном отрезке Пусть даны числа и. Требуется посчитать количество чисел в отрезке, взаимно простых с .

Сразу перейдём к обратной задаче — посчитаем количество не взаимно простых чисел.

Рассмотрим все простые делители числа; обозначим их через ().

Сколько чисел в отрезке, делящихся на? Их количество равно:

Однако если мы просто просуммируем эти числа, то получим неправильный ответ — некоторые числа будут просуммированы несколько раз (те, которые делятся сразу на несколько). Поэтому надо воспользоваться формулой включений-исключений.

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

Количество чисел в заданном отрезке, кратных хотя бы одному из заданных чисел:

Даны чисел и число. Требуется посчитать количество чисел в отрезке, которые кратны хотя бы одному из .

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

Таким образом, решение сводится к тому, чтобы за перебрать поднабор чисел, за операций найти их наименьшее общее кратное, и прибавить или вычесть из ответа очередное значение.

Количество строк, удовлетворяющих заданному числу паттернов Дано паттернов — строк одинаковой длины, состоящих только из букв и знаков вопроса. Также дано число. Требуется посчитать количество строк, удовлетворяющих ровно паттернам либо, в другой постановке, как минимум паттернам.

Заметим вначале, что мы можем легко посчитать число строк, удовлетворяющих сразу всем указанным паттернам. Для этого надо просто «пересечь» эти паттерны: посмотреть на первый символ (во всех ли паттернах на первой позиции стоит вопрос, или не во всех — тогда первый символ определён однозначно), на второй символ, и т. д.

Научимся теперь решать первый вариант задачи: когда искомые строки должны удовлетворять ровно паттернам.

Для этого переберём и зафиксируем конкретное подмножество паттернов размера — теперь мы должны посчитать количество строк, удовлетворяющих этому набору паттернов и только ему. Для этого воспользуемся формулой включений-исключений: мы суммируем по всем надмножествам множества, и либо прибавляем к текущему ответу, либо отнимаем от него количество строк, подходящих под текущее множество:

где обозначает количество строк, подходящих под набор паттернов .

Если мы просуммируем по всем, то получим ответ:

Однако тем самым мы получили решение за время порядка .

Решение можно ускорить, заметив, что в разных суммирование зачастую ведётся по одним и тем же множествам .

Перевернём формулу включений-исключений и будем вести суммирование по. Тогда легко понять, что множество учтётся в формулах включений-исключений, везде с одним и тем же знаком :

Решение получилось с асимптотикой .

Перейдём теперь ко второму варианту задачи: когда искомые строки должны удовлетворять как минимум паттернам.

Понятно, мы можем просто воспользоваться решением первого варианта задачи и просуммировать ответы от до. Однако можно заметить, что все рассуждения по-прежнему будут верны, только в этом варианте задачи сумма по идёт не только по тем множествам, размер которых равен, а по всем множествам с размером .

Таким образом, в итоговой формуле перед будет стоять другой коэффициент: не один биномиальный коэффициент с каким-то знаком, а их сумма:

Количество путей.

Есть поле, некоторые клеток которого — непроходимые стенки. На поле в клетке (левая нижняя клетка) изначально находится робот. Робот может двигаться только вправо или вверх, и в итоге он должен попасть в клетку, избежав все препятствия. Требуется посчитать число путей, которыми он может это сделать.

Предполагаем, что размеры и очень большие (скажем, до), а количество — небольшое (порядка).

Для решения сразу в целях удобства отсортируем препятствия в том порядке, в каком мы можем их обойти: т. е., например, по координате, а при равенстве — по координате .

Также сразу научимся решать задачу без препятствий: т. е. научимся считать число способов дойти от одной клетки до другой. Если по одной координате нам надо пройти клеток, а по другой — клеток, то из несложной комбинаторики мы получаем такую формулу через биномиальные коэффициенты:

Теперь чтобы посчитать число способов дойти от одной клетки до другой, избежав всех препятствий, можно воспользоваться формулой включений-исключений: посчитаем число способов дойти, наступив хотя бы на одно препятствие.

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

Однако это снова будет неполиномиальное решение — за асимптотику. Покажем, как получить полиномиальное решение.

Решать будем динамическим программированием: научимся вычислять числа — число способов дойти отой точки доой, не наступив при этом ни на одно препятствие (кроме самих и, естественно). Всего у нас будет точки, поскольку к препятствиям добавляются стартовая и конечная клетки.

Если мы на секунду забудем про все препятствия и просто посчитаем число путей из клетки в клетку, то тем самым мы учтём некоторые «плохие» пути, проходящие через препятствия. Научимся считать количество этих «плохих» путей. Переберём первое из препятствий, на которое мы наступим, тогда количество путей будет равно, умноженному на число произвольных путей из в. Просуммировав это по всем, мы посчитаем количество «плохих» путей.

Таким образом, значение мы научились считать за время. Следовательно, решение всей задачи имеет асимптотику .

Число взаимно простых четвёрок.

Дано чисел:. Требуется посчитать количество способов выбрать из них четыре числа так, что их совокупный наибольший общий делитель равен единице.

Будем решать обратную задачу — посчитаем число «плохих» четвёрок, т. е. таких четвёрок, в которых все числа делятся на число .

Воспользуемся формулой включений-исключений, суммируя количество четвёрок, делящихся на делитель (но, возможно, делящихся и на больший делитель):

где — это количество простых в факторизации числа , — количество четвёрок, делящихся на .

Чтобы посчитать функцию, надо просто посчитать количество чисел, кратных, и биномиальным коэффициентом посчитать число способов выбрать из них четвёрку.

Таким образом, с помощью формулы включений-исключений мы суммируем количество четвёрок, делящихся на простые числа, затем отнимаем число четвёрок, делящихся на произведение двух простых, прибавляем четвёрки, делящиеся на три простых, и т. д.

Число гармонических троек.

Дано число. Требуется посчитать число таких троек чисел, что они являются гармоническими тройками, т. е.:

• · либо,
• · либо,

Во-первых, сразу перейдём к обратной задаче — т. е. посчитаем число негармонических троек.

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

Таким образом, количество негармонических троек равно сумме по всем числам от до произведений количества взаимно простых с текущим числом чисел на количество не взаимно простых чисел.

Теперь всё, что нам осталось для решения задачи — это научиться считать для каждого числа в отрезке количество чисел, взаимно простых (или не взаимно простых) с ним. Хотя эта задача уже рассматривалась нами выше, описанное выше решение не подходит здесь — оно потребует факторизации каждого из чисел от до, и затем перебора всевозможных произведений простых чисел из факторизации.

Число перестановок без неподвижных точек Докажем, что число перестановок длины без неподвижных точек равно следующему числу:

и приблизительно равно числу:

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

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

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

Подставляя это в формулу включений-исключений и учитывая, что число способов выбрать подмножество размера изэлементного множества равно, получаем формулу для числа перестановок хотя бы с одной неподвижной точкой:

Тогда число перестановок без неподвижных точек равно:

Упрощая это выражение, получаем точное и приблизительное выражения для количества перестановок без неподвижных точек:

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

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