bulgakov

30. Формула включений и исключений для n множеств

Размер объединения nn множеств равен сумме размеров всех пересечений по одному множеству, минус сумма размеров всех попарных пересечений, плюс сумма всех тройных, и так далее с чередующимися знаками. Каждый элемент из объединения при этом учитывается ровно один раз — по тому же принципу, что мы проверили для трёх множеств.

Что пригодится из прошлого: включения и исключения для двух и трёх множеств — идея «добавили, вычли, вернули»; следствия бинома — знакопеременная сумма ∑(−1)k(tk)=0\sum(-1)^k\dbinom tk=0; законы де Моргана и распределительные законы — для второго доказательства. Если эти главы знакомы, читайте дальше. Если нет — загляните по ссылке, потом возвращайтесь.

Теорема

Пусть S={s1,s2,…,sN}S=\{s_1,s_2,\dots,s_N\} — конечное множество, а S1,S2,…,SnS_1,S_2,\dots,S_n — его подмножества. В формуле ниже встречаются суммы такого вида:

∑1≤i1<i2<⋯<ik≤n∣Si1∩Si2∩⋯∩Sik∣\sum_{1\le i_1<i_2<\dots<i_k\le n}|S_{i_1}\cap S_{i_2}\cap\dots\cap S_{i_k}|

— сумма размеров пересечений всех наборов из kk различных множеств. Номера в наборе записываются по возрастанию, чтобы каждый набор был учтён один раз. Таких наборов (nk)\dbinom nk.

Черта над множеством означает дополнение: Si‾\overline{S_i} — те элементы SS, которые не лежат в SiS_i (см. дополнение множества).

Теорема (принцип включений и исключений).

∣S1∪⋯∪Sn∣=∑i=1n∣Si∣−∑1≤i1<i2≤n∣Si1∩Si2∣+∑1≤i1<i2<i3≤n∣Si1∩Si2∩Si3∣−⋯+(−1)n−1∣S1∩⋯∩Sn∣.\begin{aligned} |S_1\cup\dots\cup S_n|={}&\sum_{i=1}^{n}|S_i|\\ &-\sum_{1\le i_1<i_2\le n}|S_{i_1}\cap S_{i_2}|\\ &+\sum_{1\le i_1<i_2<i_3\le n}|S_{i_1}\cap S_{i_2}\cap S_{i_3}|\\ &-\cdots+(-1)^{n-1}|S_1\cap\dots\cap S_n|. \end{aligned}

И вместе с ней

∣S1‾∩S2‾∩⋯∩Sn‾∣=∣S∣−∣S1∪⋯∪Sn∣.\bigl|\overline{S_1}\cap\overline{S_2}\cap\dots\cap\overline{S_n}\bigr|=|S|-|S_1\cup\dots\cup S_n|.

Знак перед суммой по наборам из kk множеств равен (−1)k−1(-1)^{k-1}: плюс для k=1,3,5,…k=1,3,5,\dots и минус для k=2,4,…k=2,4,\dots. Второе равенство складывается из двух простых шагов. Закон де Моргана (для двух множеств, для нескольких) даёт S1‾∩⋯∩Sn‾=S1∪⋯∪Sn‾\overline{S_1}\cap\dots\cap\overline{S_n}=\overline{S_1\cup\dots\cup S_n}: элементы, не попавшие ни в одно SiS_i, — это дополнение объединения. А в дополнении столько элементов, сколько в SS без объединения: ∣S∣−∣S1∪⋯∪Sn∣|S|-|S_1\cup\dots\cup S_n|.

Разберём на четырёх множествах

Чтобы увидеть устройство формулы, возьмём S1={1,2,3,4}S_1=\{1,2,3,4\}, S2={3,4,5,6}S_2=\{3,4,5,6\}, S3={2,4,6,8}S_3=\{2,4,6,8\}, S4={4,5,6,7}S_4=\{4,5,6,7\}. Слагаемых в формуле столько, сколько непустых наборов номеров: (41)+(42)+(43)+(44)=4+6+4+1=15=24−1\dbinom41+\dbinom42+\dbinom43+\dbinom44=4+6+4+1=15=2^4-1.

В таблице «Номера» — это номера множеств, которые пересекаем, «Элементы» — их общие элементы, «Вклад» — размер пересечения со знаком, с которым оно входит в формулу:

kk Номера Элементы Вклад
1 1 {1,2,3,4} +4
1 2 {3,4,5,6} +4
1 3 {2,4,6,8} +4
1 4 {4,5,6,7} +4
2 1,2 {3,4} −2
2 1,3 {2,4} −2
2 1,4 {4} −1
2 2,3 {4,6} −2
2 2,4 {4,5,6} −3
2 3,4 {4,6} −2
3 1,2,3 {4} +1
3 1,2,4 {4} +1
3 1,3,4 {4} +1
3 2,3,4 {4,6} +2
4 1,2,3,4 {4} −1
итого 8

Числа со знаками дают 16−12+5−1=816-12+5-1=8. Объединение {1,2,…,8}\{1,2,\dots,8\} действительно содержит 88 элементов.

Доказательство 1: по вкладу каждого элемента

Возьмём любой элемент aa множества SS и посмотрим, сколько раз он учтён в правой части формулы.

  • Если aa не лежит ни в одном SiS_i, он не попадает ни в одно пересечение: вклад 00, и в левой части его тоже нет.
  • Пусть aa лежит ровно в t≥1t\ge1 из множеств. В пересечение набора из kk множеств он входит ровно тогда, когда все kk множеств набора — из этих tt. Таких наборов (tk)\dbinom tk. Значит, вклад элемента (с учётом знаков) равен
(t1)−(t2)+(t3)−⋯+(−1)t−1(tt)=∑k=1t(−1)k−1(tk).\binom t1-\binom t2+\binom t3-\cdots+(-1)^{t-1}\binom tt=\sum_{k=1}^{t}(-1)^{k-1}\binom tk.

По формуле бинома при t≥1t\ge1 знакопеременная сумма по всем kk от 00 до tt равна нулю: ∑k=0t(−1)k(tk)=(1−1)t=0\sum_{k=0}^{t}(-1)^k\dbinom tk=(1-1)^t=0 (это следствие из главы про бином). Слагаемое с k=0k=0 равно (t0)=1\dbinom t0=1, поэтому ∑k=1t(−1)k(tk)=−1\sum_{k=1}^{t}(-1)^k\dbinom tk=-1. Вклад элемента ∑k=1t(−1)k−1(tk)\sum_{k=1}^{t}(-1)^{k-1}\dbinom tk отличается от этой суммы только знаком, то есть равен −(−1)=1-(-1)=1.

Итак, каждый элемент объединения учтён один раз, элементы вне объединения — ни разу. Правая часть равна ∣S1∪⋯∪Sn∣|S_1\cup\dots\cup S_n|. □\square

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

Доказательство 2: индукция по nn

Для n=1n=1 теорема очевидна, для n=2n=2 и n=3n=3 мы её уже проверили. Предположим, что она верна для любых n−1n-1 множеств, и докажем её для nn множеств. Обозначим X=S1∪⋯∪Sn−1X=S_1\cup\dots\cup S_{n-1}. По формуле для двух множеств

∣X∪Sn∣=∣X∣+∣Sn∣−∣X∩Sn∣.|X\cup S_n|=|X|+|S_n|-|X\cap S_n|.

Для n=3n=3 (здесь X=S1∪S2X=S_1\cup S_2) вся формула выглядит так:

∣S1∪S2∪S3∣=(∣S1∣+∣S2∣−∣S1∩S2∣)+∣S3∣−(∣S1∩S3∣+∣S2∩S3∣−∣S1∩S2∩S3∣).\begin{aligned} |S_1\cup S_2\cup S_3|&=\bigl(|S_1|+|S_2|-|S_1\cap S_2|\bigr)+|S_3|\\ &\quad-\bigl(|S_1\cap S_3|+|S_2\cap S_3|-|S_1\cap S_2\cap S_3|\bigr). \end{aligned}

Теперь разберём три слагаемых в общем случае.

  1. ∣X∣|X| — это объединение n−1n-1 множеств. По предположению оно записывается формулой, в которой участвуют все наборы номеров из 1,…,n−11,\dots,n-1.
  2. ∣Sn∣|S_n| — набор из единственного номера nn, со знаком «плюс».
  3. ∣X∩Sn∣|X\cap S_n|. По распределительному закону X∩Sn=(S1∩Sn)∪⋯∪(Sn−1∩Sn)X\cap S_n=(S_1\cap S_n)\cup\dots\cup(S_{n-1}\cap S_n) — снова объединение n−1n-1 множеств Ti=Si∩SnT_i=S_i\cap S_n. По предположению индукции их объединение раскладывается по всем наборам из 1,…,n−11,\dots,n-1, и пересечение Ti1∩⋯∩Tik=Si1∩⋯∩Sik∩SnT_{i_1}\cap\dots\cap T_{i_k}=S_{i_1}\cap\dots\cap S_{i_k}\cap S_n. Эти слагаемые — наборы номеров, содержащие nn, размера k+1k+1; перед ними в формуле для X∩SnX\cap S_n стоит знак (−1)k−1(-1)^{k-1} (набор из kk множеств TiT_i), а в нашей формуле перед всем ∣X∩Sn∣|X\cap S_n| стоит ещё минус. Итоговый знак −(−1)k−1=(−1)k-(-1)^{k-1}=(-1)^{k}. Но такое слагаемое отвечает набору из k+1k+1 множеств SiS_i (вместе с SnS_n), а требуемый знак для набора такого размера — (−1)(k+1)−1=(−1)k(-1)^{(k+1)-1}=(-1)^k. Знаки совпали.

Вместе: наборы без номера nn пришли из ∣X∣|X|; одиночный набор {n}\{n\} — из ∣Sn∣|S_n|; остальные наборы с номером nn — из ∣X∩Sn∣|X\cap S_n|. Все непустые наборы номеров из {1,…,n}\{1,\dots,n\} встретились по разу и с нужными знаками. □\square

Проверка на крайнем случае

Пусть все nn множеств совпадают с одним множеством S1S_1. Тогда объединение равно S1S_1, а в правой части все пересечения тоже равны S1S_1:

∣S1∣⋅((n1)−(n2)+(n3)−⋯ )=∣S1∣⋅1,|S_1|\cdot\Bigl(\binom n1-\binom n2+\binom n3-\cdots\Bigr)=|S_1|\cdot1,

потому что из ∑k=0n(−1)k(nk)=0\sum_{k=0}^{n}(-1)^k\dbinom nk=0 следует 1−((n1)−(n2)+(n3)−⋯ )=01-\Bigl(\dbinom n1-\dbinom n2+\dbinom n3-\cdots\Bigr)=0, то есть выражение в скобках равно 11.

Частые ошибки

  • Забыть какие-то пересечения. Слагаемых 2n−12^n-1: все непустые наборы номеров.
  • Перепутать знаки. Нечётные наборы (из 1,3,51,3,5 множеств) — плюс, чётные — минус.
  • Взять не «по возрастанию». Набор {1,3}\{1,3\} и набор {3,1}\{3,1\} — один и тот же; номера нужно перебирать так, чтобы каждый набор встретился один раз.
  • Путать ∣S1∩S2∩⋯∩Sn∣|S_1\cap S_2\cap\dots\cap S_n| и ∣S1‾∩⋯∩Sn‾∣|\overline{S_1}\cap\dots\cap\overline{S_n}|. Второе — элементы, не лежащие ни в одном SiS_i.

Проверь себя

1. Сколько слагаемых в формуле включений и исключений для пяти множеств? Сколько из них со знаком «плюс»?

Решение

Все непустые наборы номеров: 25−1=312^5-1=31. «Плюс» — наборы из 11, 33, 55 множеств: (51)+(53)+(55)=5+10+1=16\dbinom51+\dbinom53+\dbinom55=5+10+1=16. «Минус» — наборы из 22 и 44 множеств: (52)+(54)=10+5=15\dbinom52+\dbinom54=10+5=15.

2. Известно, что в множестве SS из 5050 элементов объединение ∣S1∪S2∪S3∪S4∣=42|S_1\cup S_2\cup S_3\cup S_4|=42. Сколько элементов лежит вне всех SiS_i?

Решение

∣S1‾∩S2‾∩S3‾∩S4‾∣=∣S∣−∣S1∪⋯∪S4∣=50−42=8|\overline{S_1}\cap\overline{S_2}\cap\overline{S_3}\cap\overline{S_4}|=|S|-|S_1\cup\dots\cup S_4|=50-42=8.

3. Покажите, что при n=2n=2 формула совпадает с известной.

Решение

Для n=2n=2 наборы номеров: {1}\{1\}, {2}\{2\} (плюс) и {1,2}\{1,2\} (минус): ∣S1∪S2∣=∣S1∣+∣S2∣−∣S1∩S2∣|S_1\cup S_2|=|S_1|+|S_2|-|S_1\cap S_2|.

Итог

  • ∣S1∪⋯∪Sn∣|S_1\cup\dots\cup S_n| — сумма размеров пересечений наборов из kk множеств со знаком (−1)k−1(-1)^{k-1}, по всем k=1,…,nk=1,\dots,n; слагаемых 2n−12^n-1.
  • Элементы вне всех множеств: ∣S1‾∩⋯∩Sn‾∣=∣S∣−∣S1∪⋯∪Sn∣|\overline{S_1}\cap\dots\cap\overline{S_n}|=|S|-|S_1\cup\dots\cup S_n|.
  • Доказательство 1: элемент из t≥1t\ge1 множеств учтён ∑k≥1(−1)k−1(tk)=1\sum_{k\ge1}(-1)^{k-1}\dbinom tk=1 раз.
  • Доказательство 2: индукция, ∣X∪Sn∣=∣X∣+∣Sn∣−∣X∩Sn∣|X\cup S_n|=|X|+|S_n|-|X\cap S_n| и распределительный закон.
ПрактикаЗагружаем тест…