Формула включень-виключень

Випадок двох множин

Формула включень-виключень (або принцип включень-виключень) — комбінаторна формула, що дозволяє визначити потужність об'єднання скінченного числа скінченних множин, які в загальному випадку можуть перетинатися один з одним.

Наприклад, у випадку двох множин $A$ та $B$ формула включень-виключень має вигляд:

$|A\cup B|=|A|+|B|-|A\cap B|.$

У сумі $|A|+|B|$ елементи перетину $A\cap B$ враховані двічі, тому віднімаємо $|A\cap B|$ з правої частини формули. Справедливість цього міркування видно з діаграми Ейлера-Венна для двох множин, яка наведена на малюнку праворуч.

Формула включень-виключень для трьох множин

У випадку трьох множин 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|.$

Ця формула може бути перевірена підрахунком того, скільки разів кожна область діаграми Ейлера-Венна використовується в правій частині формули. В цьому випадку, можна зауважити, що елементи перетину трьох множин будуть три рази враховані і три рази відняті, тому їх потрібно додати задля правильного підрахунку.

Таким же чином і в разі $n>3$ множин процес знаходження кількості елементів об'єднання $A_{1}\cup A_{2}\cup \ldots \cup A_{n}$ полягає у включенні всього, потім виключення зайвого, потім включенні помилково виключеного і так далі, тобто в чергуванні включення і виключення. Звідси і походить назва формули.

Історія

Вперше формулу включень-виключень опублікував португальський математик Даніель да Сільва в 1854 році. Але ще в 1713 Микола Бернуллі використовував цей метод для вирішення завдання Монмора, відомої як задача про зустрічі (фр. Le problème des rencontres), окремим випадком якої є задача про безлад. Також формулу включень-виключень пов'язують з іменами французького математика Абрахама де Муавра і англійського математика Джозефа Сильвестра. У теорії ймовірностей аналог принципу включень-виключень відомий як формула Анрі Пуанкаре.

Формулювання

Формулу включень-виключень можна сформулювати в різних формах.

У термінах множин

Нехай $A_{1},A_{2},\ldots ,A_{n}$ — скінченні множини. Формула включень-виключень стверджує:

${\biggl |}\bigcup _{i=1}^{n}A_{i}{\biggr |}=\sum _{i=1}^{n}\left|A_{i}\right|\;-\sum _{1\leqslant i<j\leqslant n}\left|A_{i}\cap A_{j}\right|\;+\sum _{1\leqslant i<j<k\leqslant n}\left|A_{i}\cap A_{j}\cap A_{k}\right|\;-\ \ldots \ +\;\left(-1\right)^{n-1}\left|A_{1}\cap \cdots \cap A_{n}\right|.$

Більш компактно можна записати так:

${\Biggl |}\bigcup _{i=1}^{n}A_{i}{\Biggr |}=\sum _{k=1}^{n}(-1)^{k+1}\left(\sum _{1\leqslant i_{1}<\cdots <i_{k}\leqslant n}\left|A_{i_{1}}\cap \cdots \cap A_{i_{k}}\right|\right)$

або

${\Biggl |}\bigcup _{i=1}^{n}A_{i}{\Biggr |}=\sum _{\emptyset \neq J\subseteq \{1,2,\ldots ,n\}}(-1)^{|J|-1}{\Biggl |}\bigcap _{j\in J}A_{j}{\Biggr |}.$

При $n=2,\ 3$ отримуємо формули для двох або трьох множин, наведені вище.

У термінах властивостей

Принцип включень-виключень часто наводять в такому альтернативному формулюванні . Нехай дано кінцеву множину $U$, яка складається з $N$ елементів, і нехай є набір властивостей $a_{1},\ldots ,a_{n}$. Кожен елемент множини $U$ може володіти або не володіти будь-якою з цих властивостей. Позначимо через $N(a_{i_{1}}\ldots a_{i_{s}})$ кількість елементів, що володіють відповідно властивостями $a_{i_{1}},\ldots ,a_{i_{s}}$ (і, можливо, деякими іншими). Також через $N({\overline {a}}_{i_{1}}\ldots {\overline {a}}_{i_{s}})$ позначимо кількість елементів, що не володіють жодною з властивостей $a_{i_{1}},\ldots ,a_{i_{s}}$. Тоді має місце формула:

$N({\overline {a}}_{1}\ldots {\overline {a}}_{n})=N-\sum _{i}N(a_{i})+\sum _{i<j}N(a_{i}a_{j})-\sum _{i<j<k}N(a_{i}a_{j}a_{k})+\ldots +(-1)^{n}N(a_{1}\ldots a_{n}).$

Формулювання принципу включень-виключень у термінах множин еквівалентне формулюванню в термінах властивостей. Дійсно, якщо множина $A_{i}$ є підмножинами деякої множини $U$, то в силу законів де Моргана $|\bigcup \nolimits _{i}A_{i}|=|U|-|\bigcap \nolimits _{i}{\overline {A_{i}}}|$ (риска над множиною позначає доповнення в множині $U$), і формулу включень-виключень можна переписати так:

${\biggl |}\bigcap _{i=1}^{n}{\overline {A_{i}}}{\biggl |}=|U|-\sum _{i}|A_{i}|+\sum _{i<j}|A_{i}\cap A_{j}|-\sum _{i<j<k}|A_{i}\cap A_{j}\cap A_{k}|+\ldots +(-1)^{n}|A_{1}\cap A_{2}\cap \ldots \cap A_{n}|.$

Якщо тепер замість «елемент $x$ належить множини $A_{i}$» говорити «елемент $x$ має властивість $a_{i}$», то ми отримаємо формулювання принципу включень-виключень в термінах властивостей, і навпаки.

Позначимо через $N(r)$ кількість елементів, що володіють в точності r властивостями з набору $a_{1},\ldots ,a_{n}$. Тоді формулу включень-виключень можна переписати в такій замкненій формі

$N(0)=\sum _{k=0}^{n}(-1)^{k}\sum _{i_{1}<\ldots <i_{k}}N(i_{1},\ldots ,i_{k}).$

Доведення

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

За математичною індукцією

Доведення за математичною індукцією.  

Формулу включень-виключень можна довести за математичною індукцією .

При $n=1$ формула включень-виключень тривіальна:

$N({\overline {a}})=N-N(a).$

Нехай формула вірна для $n=m$, доведемо її для $n=m+1$.

Нехай кожен елемент множини $U$ може володіти або мати будь-яку з властивостей $a_{1},\ldots ,a_{m},a_{m+1}$. Застосуємо формулу включень-виключень для властивостей $a_{1},\ldots ,a_{m}$:

$N({\overline {a}}_{1}\ldots {\overline {a}}_{m})=N-\sum _{i\leqslant m}N(a_{i})+\sum _{i<j\leqslant m}N(a_{i}a_{j})+\ldots +(-1)^{m}N(a_{1}\ldots a_{m}).$

Тепер застосуємо формулу для властивостей $a_{1},\ldots ,a_{m}$ до множини $N(a_{m+1})$ об'єктів, для яких виконано властивість $a_{m+1}$:

$N({\overline {a}}_{1}\ldots {\overline {a}}_{m}a_{m+1})=N(a_{m+1})-\sum _{i\leqslant m}N(a_{i}a_{m+1})+\sum _{i<j\leqslant m}N(a_{i}a_{j}a_{m+1})+\ldots +(-1)^{m}N(a_{1}\ldots a_{m}a_{m+1}).$

Нарешті, застосуємо формулу для однієї властивості $a_{m+1}$ до сукупності $N({\overline {a}}_{1}\ldots {\overline {a}}_{m})$, об'єктів, які не володіють властивостями $a_{1},\ldots ,a_{m}$:

$N({\overline {a}}_{1}\ldots {\overline {a}}_{m}{\overline {a}}_{m+1})=N({\overline {a}}_{1}\ldots {\overline {a}}_{m})-N({\overline {a}}_{1}\ldots {\overline {a}}_{m}a_{m+1}).$

Комбінуючи виписані три формули, отримаємо формулу включень-виключень для $m+1$ властивостей $a_{1},\ldots ,a_{m+1}$. Що і потрібно було довести.

Комбінаторне доведення

Доведення.  

Розглянемо довільний елемент $e\in U$ і підрахуємо, скільки разів він враховується в правій частині формули включень-виключень.

Якщо елемент $e$ не володіє жодною з властивостей $a_{i}$, то в правій частині формули він враховується рівно 1 раз (в члені $N$).

Нехай елемент $e$ володіє рівно $r$ властивостями $a_{j_{1}},\ldots ,a_{j_{r}}$. Тоді $e$ дає по 1 в тих доданків суми $\sum \nolimits _{i_{1}<\ldots <i_{s}}N(a_{i_{1}},\ldots ,a_{i_{s}})$, для яких $\{i_{1},\ldots ,i_{s}\}$ є підмножина $\{j_{1},\ldots ,j_{r}\}$, і 0 для інших. Число таких підмножин за визначенням є число сполук ${\tbinom {r}{s}}$. Отже, внесок елемента $e$ в праву частину дорівнює

$1-{r \choose 1}+{r \choose 2}-\ldots +(-1)^{n}{r \choose n}.$

При $s>r$ число сполучень дорівнює нулю. Сума, що залишилася в силу біноміальної теореми дорівнює

$\sum _{s=0}^{r}(-1)^{s}{r \choose s}={\bigg (}1+(-1){\bigg )}^{r}=0.$

Таким чином, права частина формули включень-виключень враховує кожен елемент, який не має зазначених властивостей точно по одному разу, а кожен елемент, що володіє хоча б однією з властивостей — нуль разів. Отже, вона дорівнює кількості елементів, що не володіють жодною з властивостей $a_{i}$, тобто $N({\overline {a}}_{1}\ldots {\overline {a}}_{n})$. Що і потрібно було довести.

Використовуючи індикаторні функції

Доведення.  

Нехай $A_{i}$ — довільні (не обов'язково скінченні) множини, які є підмножинами деякої множини $U$, і нехай $\mathbf {1} _{A_{i}}$ — індикаторні функції $A_{i}$ (або, еквівалентно, властивостей $a_{i}$).

Індикаторна функція їх доповнень ${\overline {A_{i}}}$ дорівнює

$\mathbf {1} _{\overline {A_{i}}}=1-\mathbf {1} _{A_{i}},$

а індикаторна функція перетину доповнень:

$\mathbf {1} _{\cap _{i}{\overline {A_{i}}}}=\prod _{i}(1-\mathbf {1} _{A_{i}}).$

Розкриваючи дужки в правій частині і ще раз використовуючи той факт, що індикаторна функція перетину множин дорівнює добутку їх індикаторних функцій, отримуємо:

$\mathbf {1} _{\bigcap _{i}{\overline {A_{i}}}}=1-\sum _{i}\mathbf {1} _{A_{i}}+\sum _{i<j}\mathbf {1} _{A_{i}\cap A_{j}}-\sum _{i<j<k}\mathbf {1} _{A_{i}\cap A_{j}\cap A_{k}}+\ldots +(-1)^{n}\mathbf {1} _{A_{1}\cap \ldots \cap A_{n}}.$

Це співвідношення — одна з форм принципу включень-виключень. Воно виражає собою логічну тотожність і вірне для довільних множин $~A_{i}$. У разі скінченних множин $A_{i}$ (і, відповідно, в припущенні скінченності множини $U$), якщо підсумувати це співвідношення по всіх $x\in U$ і скористатися тим, що для довільного підмножини $A\subset U$ його потужність дорівнює

$|A|=\sum _{x\in U}\mathbf {1} _{A}(x),$

отримаємо формулювання принципу включень-виключень в термінах потужностей множин (або в термінах властивостей).

Застосування

Задача про безлад

Класичний приклад використання формули включень-виключень — задача про безлад. Потрібно знайти число перестановок $p_{1},p_{2},\ldots ,p_{n}$ множини $\{1,2,\ldots ,n\}$ таких що $p_{i}\neq i$ для всіх $i$. Такі перестановки називаються безладом.

Нехай $U$ — множина всіх перестановок $p$ і нехай властивість $a_{i}$ перестановки виражається рівністю $p_{i}=i$. Тоді число безладів є $N({\overline {a}}_{1},{\overline {a}}_{2},\ldots ,{\overline {a}}_{n})$. Легко бачити, що $N(a_{i_{1}},\ldots ,a_{i_{s}})=(n-s)!$ — число перестановок, що залишають на місці елементи $i_{1},\ldots ,i_{s}$, і таким чином сума $\sum N(a_{i_{1}},a_{i_{2}},\ldots ,a_{i_{s}})$ містить ${\tbinom {n}{s}}$ однакових доданків. Формула включень-виключень дає вираз для числа $D_{n}$ безладів:

$D_{n}=n!-{N \choose 1}(n-1)!+{N \choose 2}(n-2)!-\ldots +(-1)^{n}{n \choose n}0!.$

Це співвідношення можна перетворити до вигляду

$D_{n}=n!\left(1-{\frac {1}{1!}}+{\frac {1}{2!}}-\ldots +{\frac {(-1)^{n}}{n!}}\right).$

Неважко бачити, що вираз в дужках є частковою сумою ряду $\sum _{k=0}^{\infty }{\frac {(-1)^{k}}{k!}}=e^{-1}$. Таким чином, з хорошою точністю число безладів становить $1/e$ частку від загального числа $P_{n}=n!$ перестановок:

$D_{n}/P_{n}\approx 1/e.$

Обчислення функції Ейлера

Інший приклад застосування формули включень-виключень — знаходження явного вираження для функції Ейлера $\varphi (n)$, що виражає кількість чисел з $1,2,\ldots ,n,$ взаємно простих з $n$.

Нехай канонічне розкладання числа $n$ на прості множники має вигляд

$n=p_{1}^{s_{1}}p_{2}^{s_{2}}\ldots p_{k}^{s_{k}}.$

Число $m\in 1,\ldots ,n$ взаємно просте з $n$ тоді і тільки тоді, коли жоден з простих дільників $p_{i}$ ділить $m$. Якщо тепер властивість $a_{i}$ означає, що $p_{i}$ ділить $m$, то кількість чисел, взаємно простих з $n$ є $N({\overline {a}}_{1},\ldots ,{\overline {a}}_{k})$.

Кількість $N(a_{i_{1}},\ldots ,a_{i_{s}})$ чисел, що володіють властивостями $a_{i_{1}},\ldots ,a_{i_{s}}$ дорівнює $n/p_{i_{1}}\ldots p_{i_{s}}$, оскільки $p_{i_{1}}|m,\ldots ,p_{i_{s}}|m\leftrightarrow p_{i_{1}}\ldots p_{i_{s}}|m$.

За формулою включень-виключень знаходимо:

$\varphi (n)=n-\sum _{i}n/p_{i}+\sum _{i,j}n/p_{i}p_{j}-\ldots +(-1)^{k}n/p_{1}\ldots p_{k}.$

Ця формула перетвориться до виду:

$\varphi (n)=n\prod _{i=1}^{k}\left(1-{\frac {1}{p_{i}}}\right).$

Варіації і узагальнення

Принцип включення-виключення для ймовірностей

Нехай $(\Omega ,{\mathfrak {F}},{\mathcal {P}})$ — імовірнісний простір. Тоді для випадкових подій $A_{1},A_{2},\ldots ,A_{n}$ виконується формула

${\mathcal {P}}{\biggl (}\bigcup _{i=1}^{n}A_{i}{\biggr )}=\sum _{i}{\mathcal {P}}(A_{i})-\sum _{i<j}{\mathcal {P}}(A_{i}\cap A_{j})+\sum _{i<j<k}{\mathcal {P}}(A_{i}\cap A_{j}\cap A_{k})+\ldots +(-1)^{n-1}\,{\mathcal {P}}\left(\bigcap _{i=1}^{n}A_{i}\right).$

Ця формула виражає принцип включень-виключень для ймовірностей. Її можна отримати з принципу включень-виключень у формі індикаторних функцій:

$\mathbf {1} _{\bigcup _{i}A_{i}}=\sum _{i}\mathbf {1} _{A_{i}}-\sum _{i<j}\mathbf {1} _{A_{i}\cap A_{j}}+\sum _{i<j<k}\mathbf {1} _{A_{i}\cap A_{j}\cap A_{k}}+\ldots +(-1)^{n-1}\,\mathbf {1} _{A_{1}\cap \ldots \cap A_{n}}.$

Нехай $A_{i}$ — події імовірнісного простору $(\Omega ,{\mathfrak {F}},{\mathcal {P}})$, тобто $A_{i}\in {\mathfrak {F}}$. Візьмемо математичне сподівання ${\mathcal {M}}$ від обох частин цього співвідношення, і, скориставшись лінійністю математичного сподівання і рівністю ${\mathcal {P}}(A)={\mathcal {M}}(\mathbf {1} _{A})$ для довільного події $A\in {\mathfrak {F}}$, отримаємо формулу включення-виключення для ймовірностей.

Принцип включень-виключень у просторах з мірою

Нехай $(X,{\mathfrak {S}},\mu )$ — простір з мірою. Тоді для довільних вимірних множин $A_{i}$ кінцевої міри $\mu (A_{i})<\infty$ має місце формула включень-виключень:

$\mu {\biggl (}\bigcup _{i=1}^{n}A_{i}{\biggr )}=\sum _{i}\mu (A_{i})-\sum _{i<j}\mu (A_{i}\cap A_{j})+\sum _{i<j<k}\mu (A_{i}\cap A_{j}\cap A_{k})+\ldots +(-1)^{n-1}\,\mu \left(\bigcap _{i=1}^{n}A_{i}\right).$

Очевидно, принцип включень-виключень для ймовірностей і для потужностей скінченних множин є окремими випадками цієї формули. У першому випадку мірою є, природно, ймовірнісна міра у відповідному ймовірнісному простору: $\mu (A)={\mathcal {P}}(A)$. У другому випадку як міра береться потужність множини: $\mu (A)=|A|$.

Вивести принцип включень-виключень для просторів з мірою можна також, як для зазначених окремих випадків, з тотожності для індикаторних функцій:

$\mathbf {1} _{\bigcup _{i}A_{i}}=\sum _{i}\mathbf {1} _{A_{i}}-\sum _{i<j}\mathbf {1} _{A_{i}\cap A_{j}}+\sum _{i<j<k}\mathbf {1} _{A_{i}\cap A_{j}\cap A_{k}}+\ldots +(-1)^{n-1}\,\mathbf {1} _{A_{1}\cap \ldots \cap A_{n}}.$

Нехай $A_{i}$ — вимірні множини простору $(X,{\mathfrak {S}},\mu )$, тобто $A_{i}\in {\mathfrak {S}}$. Проінтегруємо обидві частини цієї рівності по мірі $\mu$, скористаємось лінійністю інтеграла і співвідношенням $\mu (A)=\int _{X}\mathbf {1} _{A}(x)\,d\mu$, і отримаємо формулу включень-виключень для міри.

Тотожність максимумів і мінімумів

Формула включень-виключень може розглядатися як окремий випадок тотожності максимумів і мінімумів:

$\max(a_{1},\ldots ,a_{n})=\sum _{i}a_{i}-\sum _{i<j}\min(a_{i},a_{j})+\ldots +(-1)^{n-1}\,\min(a_{1},\ldots ,a_{n}).$

Це співвідношення справедливо для довільних чисел $a_{i}$. В окремому випадку, коли $a_{i}\in \{0,1\}$ ми отримуємо одну з форм принципу включень-виключень. Справді, якщо покласти $a_{i}=\mathbf {1} _{A_{i}}(x)$, де $x$ — довільний елемент із $U$, то отримаємо співвідношення для індикаторних функцій множин:

$\mathbf {1} _{\bigcup _{i}A_{i}}(x)=\sum _{i}\mathbf {1} _{A_{i}}(x)-\sum _{i<j}\mathbf {1} _{A_{i}\cap A_{j}}(x)+\sum _{i<j<k}\mathbf {1} _{A_{i}\cap A_{j}\cap A_{k}}(x)+\ldots +(-1)^{n-1}\,\mathbf {1} _{A_{1}\cap \ldots \cap A_{n}}(x).$

Обертання Мебіуса

Нехай $S$ — кінцева множина, і нехай $f\colon 2^{S}\to \mathbb {R}$ — довільна функція, визначена на сукупності підмножин $S$, яка приймає дійсні значення. Визначимо функцію $g\colon 2^{S}\to \mathbb {R}$ наступним співвідношенням:

$g(Y)=\sum _{X\supset Y}f(X).$

Тоді має місце наступна формула звернення :

$f(Y)=\sum _{X\supset Y}(-1)^{|X|-|Y|}\,g(X).$

Це твердження є окремим випадком загальної формули обертання Мебіуса для алгебри інцидентності сукупності $2^{S}$ всіх підмножин множини $S$, частково впорядкованих по відношенню включення $\subset$.

Покажемо, як з цієї формули отримати принцип включення-виключення для скінченних множин. Нехай дано сімейство підмножин $A_{1},\ldots ,A_{n}$ скінченної множини $U$, позначимо $S=\{1,\ldots ,n\}$ — множина індексів. Для кожного набору індексів $X\subset S$ визначимо $f(X)$ як число елементів, що входять тільки в ті множини $A_{i}$, для яких $i\in X$. Математично це можна записати так:

$f(X)=\left|\left(\bigcap _{i\in X}A_{i}\right)\cap \left(\bigcap _{j\notin X}{\overline {A_{j}}}\right)\right|.$

Тоді функція $g\colon 2^{S}\to \mathbb {R}$, яка визначається формулою

$g(Y)=\sum _{X\supset Y}f(X),$

описує кількість елементів, кожний з яких входить у всі множини $A_{i}$, $i\in X$ і, бути може, ще в інші. Тобто

$g(X)=\left|\bigcap _{i\in X}A_{i}\right|.$

Зауважимо далі, що $f(\varnothing )$ — кількість елементів, що не володіють жодною з властивостей:

$f(\varnothing )=\left|\bigcap _{i}{\overline {A_{i}}}\right|.$

З урахуванням зроблених зауважень запишемо формулу обернення Мебіуса:

$\left|\bigcap _{i}{\overline {A_{i}}}\right|=\sum _{X}(-1)^{|X|}\,\left|\bigcap _{i\ inX}A_{i}\right|.$

Це є в точності формула включень-виключень для скінченних множин, тільки в ній не згруповані доданки, пов'язані з однаковим значенням $|X|$.

Див. також

• Формула Грассмана
• Нерівність Буля

Посилання

• И. Яглом. Заплаты на кафтане // Квант. — 1974. — № 2. — С. 13—21.
• Weisstein, Eric W. Inclusion-Exclusion Principle(англ.) на сайті Wolfram MathWorld.