MAXimal

добавлено: 25 Aug 2011 13:55
редактировано: 22 Oct 2011 19:29

Принцип включений-исключений

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

Формулировки принципа включений-исключений

Словесная формулировка

Принцип включений-исключений выглядит следующим образом:

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

Формулировка в терминах множеств

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

\left| \bigcup_{i=1}^n A_i \right| = \sum_{i=1}^n[...]

Её можно записать более компактно, через сумму по подмножествам. Обозначим через B множество, элементами которого являются A_i. Тогда принцип включений-исключений принимает вид:

\left| \bigcup_{i=1}^n A_i \right| = \sum_{C \sub[...]

Эту формулу приписывают Муавру (Abraham de Moivre).

Формулировка с помощью диаграмм Венна

Пусть на диаграмме отмечены три фигуры A, B и C:

Тогда площадь объединения A \cup B \cup C равна сумме площадей A, B и C за вычетом дважды покрытых площадей A \cap B, A \cap C, B \cap C, но с прибавлением трижды покрытой площади A \cap B \cap C:

S(A \cup B \cup C) = S(A) ~ + ~ S(B) ~ + ~ S(C) ~[...]

Аналогичным образом это обобщается и на объединение n фигур.

Формулировка в терминах теории вероятностей

Если A_i (i = 1 \ldots n) — это события, {\cal P}(A_i) — их вероятности, то вероятность их объединения (т.е. того, что произойдёт хотя бы одно из этих событий) равна:

\begin{eqnarray} {\cal P} \left( \bigcup_{i=1}^n[...]

Эту сумму также можно записать в виде суммы по подмножествам множества B, элементами которого являются события A_i:

{\cal P} \left( \bigcup_{i=1}^n A_i \right) = \su[...]

Доказательство принципа включений-исключений

Для доказательства удобно пользоваться математической формулировкой в терминах теории множеств:

\left| \bigcup_{i=1}^n A_i \right| = \sum_{C \sub[...]

где B, напомним, — это множество, состоящее из A_i-ых.

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

Рассмотрим произвольный элемент x, содержащийся ровно в k \ge 1 множествах A_i. Покажем, что он посчитается формулой ровно один раз.

Заметим, что:

  • в тех слагаемых, у которых size(C) = 1, элемент x учтётся ровно k раз, со знаком плюс;

  • в тех слагаемых, у которых size(C) = 2, элемент x учтётся (со знаком минус) ровно C_k^2 раз — потому что x посчитается только в тех слагаемых, которые соответствуют двум множествам из k множеств, содержащих x;

  • в тех слагаемых, у которых size(C) = 3, элемент x учтётся ровно C_k^3 раз, со знаком плюс;

  • \ldots

  • в тех слагаемых, у которых size(C) = k, элемент x учтётся ровно C_k^k раз, со знаком (-1)^{k-1};

  • в тех слагаемых, у которых size(C) > k, элемент x учтётся ноль раз.

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

T = C_k^1 - C_k^2 + C_k^3 - \ldots + (-1)^{i-1} \[...]

Проще всего посчитать эту сумму, сравнив её с разложением в бином Ньютона выражения (1-x)^k:

(1-x)^k = C_k^0 - C_k^1 \cdot x + C_k^2 \cdot x^2[...]

Видно, что при x=1 выражение (1-x)^k представляет собой не что иное, как 1 - T. Следовательно, T = 1 - (1-1)^k = 1, что и требовалось доказать.

Применения при решении задач

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

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

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

Простая задачка о перестановках

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

Посчитаем число "плохих" перестановок, т.е. таких, у которых первый элемент \le 1 и/или последний \ge 8.

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

|X| + |Y| - |X \cap Y|.

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

2 \cdot 9! + 2 \cdot 9! - 2 \cdot 2 \cdot 8!

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

Простая задачка о (0,1,2)-последовательностях

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

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

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

|A_0| + |A_1| + |A_2| - |A_0 \cap A_1| - |A_0 \ca[...]

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

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

3^n - 3 \cdot 2^n + 3 \cdot 1 - 0.

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

Дано уравнение:

x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = 20,

где все 0 \le x_i \le 8 (где i = 1 \ldots 6).

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

Забудем сначала про ограничение x_i \le 8, и просто посчитаем число неотрицательных решений этого уравнения. Это легко делается через биномиальные коэффициенты — мы хотим разбить 20 элементов на 6 групп, т.е. распределить 5 "стенок", разделяющих группы, по 25 местам:

N_0 = C_{25}^5

Посчитаем теперь по формуле включений-исключений число "плохих" решений, т.е. таких решений уравнения, в которых один или более x_i больше 9.

Обозначим через A_k (где k = 1 \ldots 6) множество таких решений уравнения, в которых x_k \ge 9, а все остальные x_i \ge 0 (для всех i \ne k). Чтобы посчитать размер множества A_k, заметим, что у нас по сути та же комбинаторная задача, что решалась двумя абзацами выше, только теперь 9 элементов исключены из рассмотрения и точно принадлежат первой группе. Таким образом:

| A_k | = C_{16}^5

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

\left| A_k \cap A_p \right| = C_7^5

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

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

C_{25}^5 - C_6^1 \cdot C_{16}^5 + C_6^2 \cdot C_7[...]

Количество взаимно простых чисел в заданном отрезке

Пусть даны числа n и r. Требуется посчитать количество чисел в отрезке [1; r], взаимно простых с n.

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

Рассмотрим все простые делители числа n; обозначим их через p_i (i = 1 \ldots k).

Сколько чисел в отрезке [1;r], делящихся на p_i? Их количество равно:

\left\lfloor \frac{ r }{ p_i } \right\rfloor

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

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

Итоговая реализация для подсчёта количества взаимно простых чисел:

int solve (int n, int r) {
	vector<int> p;
	for (int i=2; i*i<=n; ++i)
		if (n % i == 0) {
			p.push_back (i);
			while (n % i == 0)
				n /= i;
		}
	if (n > 1)
		p.push_back (n);
 
	int sum = 0;
	for (int msk=1; msk<(1<<p.size()); ++msk) {
		int mult = 1,
			bits = 0;
		for (int i=0; i<(int)p.size(); ++i)
			if (msk & (1<<i)) {
				++bits;
				mult *= p[i];
			}
 
		int cur = r / mult;
		if (bits % 2 == 1)
			sum += cur;
		else
			sum -= cur;
	}
 
	return r - sum;
}

Асимптотика решения составляет O (\sqrt{n}).

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

Даны n чисел a_i и число r. Требуется посчитать количество чисел в отрезке [1; r], которые кратны хотя бы одному из a_i.

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

Таким образом, решение сводится к тому, чтобы за 2^n перебрать поднабор чисел, за O(n \log r) операций найти их наименьшее общее кратное, и прибавить или вычесть из ответа очередное значение.

Количество строк, удовлетворяющих заданному числу паттернов

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

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

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

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

ans(X) = \sum_{Y \supseteq X} (-1)^{|Y|-k} \cdot [...]

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

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

ans = \sum_{X ~ : ~ |X| = k} ans(X).

Однако тем самым мы получили решение за время порядка O(3^k \cdot k).

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

Перевернём формулу включений-исключений и будем вести суммирование по Y. Тогда легко понять, что множество Y учтётся в C_{|Y|}^k формулах включений-исключений, везде с одним и тем же знаком (-1)^{|Y|-k}:

ans = \sum_{Y ~ : ~ |Y| \ge k} (-1)^{|Y|-k} \cdot[...]

Решение получилось с асимптотикой O(2^k \cdot k).

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

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

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

(-1)^{|Y|-k} \cdot C_{|Y|}^k ~~ + ~~ (-1)^{|Y|-k-[...]

Заглянув в Грэхема (Грэхем, Кнут, Паташник. "Конкретная математика" [1998] ), мы видим такую известную формулу для биномиальных коэффициентов:

\sum_{k=0}^m (-1)^k \cdot C_n^k = (-1)^m \cdot C_[...]

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

(-1)^{|Y|-k} \cdot C_{|Y|-1}^{|Y|-k}.

Таким образом, для этого варианта задачи мы также получили решение с асимптотикой O(2^k \cdot k):

ans = \sum_{Y ~ : ~ |Y| \ge k} (-1)^{|Y|-k} \cdot[...]

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

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

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

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

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

C_{x+y}^{x}

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

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

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

Решать будем динамическим программированием: научимся вычислять числа d[i][j] — число способов дойти от i-ой точки до j-ой, не наступив при этом ни на одно препятствие (кроме самих i и j, естественно). Всего у нас будет k+2 точки, поскольку к препятствиям добавляются стартовая и конечная клетки.

Если мы на секунду забудем про все препятствия и просто посчитаем число путей из клетки i в клетку j, то тем самым мы учтём некоторые "плохие" пути, проходящие через препятствия. Научимся считать количество этих "плохих" путей. Переберём первое из препятствий i < t < j, на которое мы наступим, тогда количество путей будет равно d[i][t], умноженному на число произвольных путей из t в j. Просуммировав это по всем t, мы посчитаем количество "плохих" путей.

Таким образом, значение d[i][j] мы научились считать за время O(k). Следовательно, решение всей задачи имеет асимптотику O(k^3).

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

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

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

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

ans = \sum_{d \ge 2} (-1)^{deg(d)-1} \cdot f(d),

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

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

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

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

Дано число n \le 10^6. Требуется посчитать число таких троек чисел 2 \le a < b < c \le n, что они являются гармоническими тройками, т.е.:

  • либо {\rm gcd}(a,b) = {\rm gcd}(a,c) = {\rm gcd}(b,c) = 1,
  • либо {\rm gcd}(a,b) > 1, {\rm gcd}(a,c) > 1, {\rm gcd}(b,c) > 1.

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

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

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

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

Поэтому нам понадобится более быстрое решение, которое подсчитывает ответы для всех чисел из отрезка [2;n] сразу.

Для этого можно реализовать такую модификацию решета Эратосфена:

  • Во-первых, нам надо найти все числа в отрезке [2;n], в факторизации которых никакое простое не входит дважды. Кроме того, для формулы включений-исключений нам потребуется знать, сколько простых содержит факторизация каждого такого числа.

    Для этого нам надо завести массивы deg[], хранящие для каждого числа количество простых в его факторизации, и good[] — содержащий для каждого числа true или false — все простые входят в него в степени \le 1 или нет.

    После этого во время решета Эратосфена при обработке очередного простого числа мы пройдёмся по всем числам, кратным текущему числу, и увеличим deg[] у них, а у всех чисел, кратных квадрату от текущего простого — поставим good = false.

  • Во-вторых, нам надо посчитать ответ для всех чисел от 2 до n, т.е. массив cnt[] — количество чисел, не взаимно простых с данным.

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

    Итак, пусть у нас есть число i, для которого good[]=true, т.е. это число, участвующее в формуле включений-исключений. Переберём все числа, кратные i, и к ответу cnt[] каждого из таких чисел мы должны прибавить или вычесть величину \lfloor N/i \rfloor. Знак — прибавление или вычитание — зависит от deg[i]: если deg[i] нечётна, то надо прибавлять, иначе вычитать.

Реализация:

int n;
bool good[MAXN];
int deg[MAXN], cnt[MAXN];
 
long long solve() {
	memset (good, 1, sizeof good);
	memset (deg, 0, sizeof deg);
	memset (cnt, 0, sizeof cnt);
 
	long long ans_bad = 0;
	for (int i=2; i<=n; ++i) {
		if (good[i]) {
			if (deg[i] == 0)  deg[i] = 1;
			for (int j=1; i*j<=n; ++j) {
				if (j > 1 && deg[i] == 1)
					if (j % i == 0)
						good[i*j] = false;
					else
						++deg[i*j];
				cnt[i*j] += (n / i) * (deg[i]%2==1 ? +1 : -1);
			}
		}
		ans_bad += (cnt[i] - 1) * 1ll * (n-1 - cnt[i]);
	}
 
	return (n-1) * 1ll * (n-2) * (n-3) / 6 - ans_bad / 2;
}

Асимптотика такого решения составляет O (n \log n), поскольку почти для каждого числа i оно совершает примерно n/i итераций вложенного цикла.

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

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

n! - C_n^1 \cdot (n-1)! + C_n^2 \cdot (n-2)! - C_[...]

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

\frac{ n! }{ e }

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

Обозначим через A_k множество перестановок длины n с неподвижной точкой в позиции k (1 \le k \le n).

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

\left| A_p \right| = (n-1)! ~,
\left| A_p \cap A_q \right| = (n-2)! ~,
\left| A_p \cap A_q \cap A_r \right| = (n-3)! ~,
\ldots ~,

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

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

C_n^1 \cdot (n-1)! - C_n^2 \cdot (n-2)! + C_n^3 \[...]

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

n! - C_n^1 \cdot (n-1)! + C_n^2 \cdot (n-2)! - C_[...]

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

n! \left( 1 - \frac{1}{1!} + \frac{1}{2!} - \frac[...]

(поскольку сумма в скобках — это первые n+1 членов разложения в ряд Тейлора e^{-1})

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

Задачи в online judges

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

Литература