2.1: Формула включення-виключення

Повернемося до проблеми, яку ми згадали, але не вирішили:

Приклад \(\PageIndex{1}\)

Скільки підмножин мультимножини\(\{2\cdot a, 4\cdot b, 3\cdot c\}\) мають розмір 7?

Рішення

Ми переказуємо проблему: це кількість рішень\(x_1+x_2+x_3=7\) з\(0\le x_1\le 2\),\(0\le x_2\le 4\),\(0\le x_3\le 3\). Ми знаємо, що кількість розв'язків в невід'ємних цілих числах є\({7+3-1\choose 3-1}={9\choose 2}\), так що це перерахунок, так як ми підраховуємо рішення, які не відповідають обмеженням верхньої межі. Наприклад, це включає деякі рішення з\(x_1\ge 3\); скільки їх існує? Це проблема, яку ми можемо вирішити: це кількість рішень\(x_1+x_2+x_3=7\) з\(3\le x_1\),\(0\le x_2\),\(0\le x_3\). Це те ж саме, що і кількість ненегативних рішень\(y_1+y_2+y_3=7-3=4\), або\({4+3-1\choose 3-1}={6\choose 2}\). Таким чином,\({9\choose 2}-{6\choose 2}\) виправляє цей перерахунок.

Якщо ми так само коректуємо для перерахунку рішень з\(x_2\ge 5\) і\(x_3\ge 4\), ми отримаємо\({9\choose 2}-{6\choose 2}-{4\choose 2}-{5\choose 2}\). Чи правильно це? Не обов'язково, тому що зараз у нас є потенційний недолік: ми двічі віднімали 1 для рішення, в якому обидва\(x_1\ge 3\) і\(x_2\ge 5\), коли ми повинні були відняти тільки 1. Однак, на щастя, таких рішень немає, так як\(3+5>7\). Але те ж саме стосується і інших пар змінних: Скільки рішень мають\(x_1\ge 3\) і\(x_3\ge 4\)? Нескладно помітити, що є тільки одне таке рішення, а саме\(3+0+4=7\). Нарешті, немає рішень з\(x_2\ge 5\) і\(x_3\ge 4\), тому виправлений підрахунок зараз\({9\choose 2}-{6\choose 2}-{4\choose 2}-{5\choose 2}+1\). При цьому не враховуються будь-які рішення\(x_1\ge 3\), в яких\(x_2\ge 5\)\(x_3\ge 4\), і, але їх немає, тому фактичний підрахунок

\[{9\choose 2}-{6\choose 2}-{4\choose 2}-{5\choose 2}+1= 36-15-6-10+1=6.\nonumber\]

Це досить мало, що це не важко перевірити, перерахувавши всі рішення.

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

Почнемо з перефразування прикладу. \(S\)Дозволяти бути сукупністю всіх ненегативних рішень\(x_1+x_2+x_3=7\), нехай\(A_1\) будуть всі рішення з\(x_1\ge 3\),\(A_2\) всі рішення з\(x_2\ge 5\), і\(A_3\) всі рішення с\(x_3\ge 4\). Ми хочемо знати розмір, рішення\(A_1^c\cap A_2^c\cap A_3^c\), для яких це неправда, що\(x_1\ge 3\) і не правда, що\(x_2\ge 5\) і не правда, що\(x_3\ge 4\). Вивчаючи наше рішення, ми бачимо, що остаточний підрахунок

\[\eqalign{ |S|-|A_1|&-|A_2|-|A_3|+|A_1\cap A_2|+|A_1\cap A_3|+|A_2\cap A_3|- |A_1\cap A_2\cap A_3|\cr &=36-15-6-10+0+1+0-0.\cr }\nonumber\]

Ця закономірність є повністю загальною:

Теорема \(\PageIndex{1}\): The Inclusion-Exclusion Formula

Якщо\(A_i\subseteq S\) для\(1\le i\le n\) то\[|A_1^c\cap\cdots\cap A_n^c|= |S|-|A_1|-\cdots-|A_n|+|A_1\cap A_2|+\cdots-|A_1\cap A_2\cap A_3|-\cdots,\nonumber\] або більш компактно:\[|\bigcap_{i=1}^n A_i^c|=|S|+\sum_{k=1}^n (-1)^k \sum|\bigcap_{j=1}^k A_{i_j}|,\nonumber\] де внутрішня сума знаходиться над усіма\(\{i_1,i_2,\ldots,i_k\}\) підмножинами\(\{1,2,\ldots,n\}\).

Доказ

Нам потрібно показати, що кожен елемент\(\bigcap_{i=1}^n A_i^c\) підраховується один раз правою стороною, а кожен інший елемент\(S\) підраховується нуль разів. Перший з них простий: якщо\(x\in \bigcap_{i=1}^n A_i^c\) то для кожного\(i\)\(x\notin A_i\), так не в\(x\) жодному з наборів за участю\(A_i\) на правій стороні, і так\(x\) зараховується, один раз, за терміном\(|S|\).

Тепер припустимо\(x\notin \bigcap_{i=1}^n A_i^c\). З правого боку,\(x\) підраховується один раз за терміном\(|S|\). Для деяких значень\(i_1,i_2,\ldots,i_k\)\(x\in A_{i_m}\),\(1\le m\le k\),, і\(x\) немає в інших наборах\(A_i\). Потім\(x\) підраховується нульовий раз будь-яким терміном, що включає в\(i\notin \{i_1,i_2,\ldots,i_k\}\) себе, і зараховується один раз, позитивно або негативно, кожним терміном, що включає тільки\(A_{i_1},A_{i_2},\ldots,A_{i_k}\).\(A_i\) Існують\(k\) терміни форми\(-|A_{i_m}|\), які\(x\) підраховують в цілому\(-k\) раз. Існують\(k\choose 2\) терміни форми\(|A_{i_l}\cap A_{i_m}|\), що\(x\) підраховують загальну кількість\(k\choose 2\) разів. Продовжуючи таким чином, ми бачимо, що остаточний підрахунок для\(x\) правого боку

\[1-k+{k\choose 2}-{k\choose 3}+\cdots+(-1)^k{k\choose k},\nonumber\]

або більш компактно

\[\sum_{i=0}^k (-1)^i{k\choose i}.\nonumber\]Ми знаємо, що ця змінна сума біноміальних коефіцієнтів дорівнює нулю, тому\(x\) підраховується нуль разів, за бажанням. (Див. Рівняння 1.4.1.)

Іноді корисна альтернативна форма формули виключення включення.

Слідство \(\PageIndex{1}\)

Якщо\(A_i\subseteq S\) для\(1\le i\le n\) то\[|\bigcup_{i=1}^n A_i|=\sum_{k=1}^n (-1)^{k+1} \sum|\bigcap_{j=1}^k A_{i_j}|,\nonumber\], де внутрішня сума знаходиться над усіма\(\{i_1,i_2,\ldots,i_k\}\) підмножинами\(\{1,2,\ldots,n\}\).

Доказ

З тих пір\((\bigcup_{i=1}^n A_i)^c=\bigcap_{i=1}^n A_i^c\),

\[\eqalign{ |\bigcup_{i=1}^n A_i|&=|S|-|\bigcap_{i=1}^n A_i^c|\cr &=|S|-(|S|+\sum_{k=1}^n (-1)^k \sum|\bigcap_{j=1}^k A_{i_j}|)\cr &=(-1)\sum_{k=1}^n (-1)^k \sum|\bigcap_{j=1}^k A_{i_j}|\cr &=\sum_{k=1}^n (-1)^{k+1}\sum|\bigcap_{j=1}^k A_{i_j}|. }\nonumber\]

Оскільки права частина формули включення-виключення складається з\(2^n\) термінів, які потрібно додати, вона все ще може бути досить нудною. У деяких приємних випадках всі перехрестя однакової кількості наборів мають однаковий розмір. Так як\(n\choose k\) можливі перетину, що складаються з\(k\) множин, формула\(m_k\) стає\[\label{eq:1}\eqalignno{ |\bigcap_{i=1}^n A_i^c|&=|S|+\sum_{k=1}^n (-1)^k{n\choose k}m_k,\cr }\] де розмір\(k\) перетину множин.

Приклад\(\PageIndex{2}\)

Знайти кількість рішень для\(x_1+x_2+x_3+x_4=25\),\(0\le x_i\le 10\). \(A_i\)Дозволяти будуть рішення\(x_1+x_2+x_3+x_4=25\) з\(x_i\ge 11\). Кількість рішень з\(x_i\ge 0\) для всіх\(i\) є\({25+4-1\choose 4-1}={25+3\choose 3}\). Також\(|A_i|={14+3\choose 3}\), і\(|A_i\cap A_j|={3+3\choose 3}\). Немає розв'язків з 3 або 4 змінними, більшими за 10. Звідси і кількість рішень

\[{25+3\choose 3}-{4\choose 1}{14+3\choose 3}+{4\choose 2}{3+3\choose 3}=676.\nonumber\]

Дописувачі та атрибуція

• Template:ContribGuichard