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

[[Файл:Venn A intersect B.svg|thumb|Випадок двох множин]]
'''Формула включень-виключень''' (або '''принцип включень-виключень''')&nbsp;— [[Комбінаторика|комбінаторна]] формула, що дозволяє визначити [[Потужність множини#Потужність скінченних множин|потужність]] [[Об'єднання множин|об'єднання]] скінченного числа [[Скінченна множина|скінченних множин]], які в загальному випадку можуть [[Перетин множин|перетинатися]] один з одним.

Наприклад, у випадку двох множин <math>A</math> та <math>B </math> формула включень-виключень має вигляд:
:<math> | A \cup B | = | A | + | B | - | A \cap B |. </math>

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

[[Файл:Inclusion-exclusion.svg|thumb|Формула включень-виключень для трьох множин]]
У випадку трьох множин ''A'', ''B'' та ''C'' формула має вигляд:
:<math>|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|.</math>

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

Таким же чином і в разі <math>n>3</math> множин процес знаходження кількості елементів об'єднання <math> A_1 \cup A_2 \cup \ldots \cup A_n </math> полягає у включенні всього, потім виключення зайвого, потім включенні помилково виключеного і так далі, тобто в чергуванні включення і виключення. Звідси і походить назва формули.

== Історія ==
Вперше формулу включень-виключень опублікував португальський математик {{Нп |  Даніель да Сільва||  en| Daniel da Silva (mathematician) }} в 1854 році<ref name = "Riordan"> {{книга 
| Автор = Ріордан Дж. 
| Заголовок = Введення в комбінаторний аналіз 
| Оригінал = An Introduction to Combinatorial Analysis 
| Місце = М. 
| Видавництво = Вид-во іноземної літератури 
| Рік = 1963 
| Сторінки = 63-66 
| Сторінок = 289 
}} </ref>.
Але ще в [[1713]] [[Микола I Бернуллі|Микола Бернуллі]] використовував цей метод для вирішення завдання [[П'єр де Монмор|Монмора]], відомої як [[Число зустрічей (комбінаторика)|задача про зустрічі]] ({{lang-fr | Le problème des rencontres}})<ref> {{MathWorld | urlname = Derangement | title = Derangement}} </ref>, окремим випадком якої є задача про [[Безлад (перестановка)|безлад]]. Також формулу включень-виключень пов'язують з іменами французького математика [[Абрахам де Муавр|Абрахама де Муавра]] і англійського математика [[Джеймс Джозеф Сильвестр|Джозефа Сильвестра]]<ref name = "Гнєденко">{{Гнєденко.Курс теорії ймовірностей}}</ref>.
У теорії ймовірностей аналог принципу включень-виключень відомий як формула [[Анрі Пуанкаре]]<ref>
{{книга 
|автор        = Ріордан Дж. 
|заголовок     = Введення в комбінаторний аналіз 
|оригінал     = An Introduction to Combinatorial Analysis
|місце        = М. 
|видавництво = Вид-во іноземної літератури 
|рік          = 1963
|сторінок      = 289
|посилання       = http://eqworld.ipmnet.ru/ru/library/books/Riordan1963ru.djvu
}}</ref>.

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

=== У термінах множин ===
Нехай <math> A_1, A_2, \ldots, A_n </math>&nbsp;— [[Скінченна множина|скінченні множини]]. Формула включень-виключень стверджує:
:<math>
\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|.
</math>

Більш компактно можна записати так:
:::<math>
\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)
</math>
або
:::<math>
\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|.
</math>

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

=== У термінах властивостей ===
Принцип включень-виключень часто наводять в такому альтернативному формулюванні
<ref name = "Hall-2.1"> {{книга 
| Автор = Холл М. 
| Заголовок= Комбінаторика 
| Оригінал = Combinatorial Theory 
| Місце = М. 
| Видавництво = «Мир» 
| Рік = 1970 
| Сторінки = 18-20 
| Сторінок = 424 
}} </ref>.
Нехай дано кінцеву множину <math>U </math>, яка складається з <math>N </math> елементів, і нехай є набір властивостей <math>a_1, \ldots, a_n</math>. Кожен елемент множини <math>U </math> може володіти або не володіти будь-якою з цих властивостей. Позначимо через <math>N (a_ {i_1} \ldots a_ {i_s}) </math> кількість елементів, що володіють відповідно властивостями <math> a_ {i_1}, \ldots, a_ {i_s} </math> (і, можливо, деякими іншими). Також через <math>N (\overline{a}_{i_1} \ldots \overline{a}_{i_s}) </math> позначимо кількість елементів, що не володіють жодною з властивостей <math> a_ {i_1} , \ldots, a_ {i_s} </math>. Тоді має місце формула:
<center>
<math> 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). </math>
</center>

Формулювання принципу включень-виключень у термінах множин еквівалентне формулюванню в термінах властивостей.
Дійсно, якщо множина <math>A_i </math> є підмножинами деякої множини <math>U </math>, то в силу [[Закони де Моргана|законів де Моргана]] <math> |\bigcup \nolimits_{ i} A_i | = | U | - | \bigcap \nolimits_ {i} \overline {A_i} | </math> (риска над множиною позначає [[Доповнення (теорія множин)|доповнення]] в множині <math>U </math>), і формулу включень-виключень можна переписати так:
<center>
<math> \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 |.</math>
</center>

Якщо тепер замість «елемент <math>x </math> належить множини <math>A_i </math>» говорити «елемент <math>x </math> має властивість <math>a_i </math>», то ми отримаємо формулювання принципу включень-виключень в термінах властивостей, і навпаки.

Позначимо через <math>N(r) </math> кількість елементів, що володіють ''в точності'' r властивостями з набору <math>a_1, \ldots, a_n</math>. Тоді формулу включень-виключень можна переписати в такій [[Вираз замкненого вигляду|замкненій формі]]
<center>
<math> N (0) = \sum_ {k = 0} ^ {n} (-1) ^ {k} \sum_ {i_1 <\ldots <i_k} N (i_1, \ldots, i_k). </math>
</center>

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

=== За математичною індукцією ===
{{Hider|
  title = Доведення за математичною індукцією. |
  hidden =1 |
  content =
Формулу включень-виключень можна довести за [[Математична індукція|математичною індукцією]]
<ref name = "Riordan"/>.

При <math>n = 1 </math> формула включень-виключень тривіальна:
<center>
<math> N (\overline {a}) = N - N (a). </math>
</center>

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

Нехай кожен елемент множини <math>U </math> може володіти або мати будь-яку з властивостей <math>a_1, \ldots, a_m, a_ {m +1}</math>.
Застосуємо формулу включень-виключень для властивостей <math>a_1, \ldots, a_m </math>:
<center>
<math> 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). </math>
</center>

Тепер застосуємо формулу для властивостей <math>a_1, \ldots, a_m </math> до множини <math>N (a_{m +1}) </math> об'єктів, для яких виконано властивість <math>a_ { m +1} </math>:
<center>
<math> 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}). </math>
</center>

Нарешті, застосуємо формулу для однієї властивості <math>a_{m +1} </math> до сукупності <math> N (\overline {a} _1 \ldots \overline {a} _m) </math>, об'єктів, які не володіють властивостями <math> a_1, \ldots, a_m </math>:
<center>
<math> 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}). </math>
</center>

Комбінуючи виписані три формули, отримаємо формулу включень-виключень для <math>m +1 </math> властивостей <math>a_1, \ldots, a_{m +1} </math>. Що і потрібно було довести.
|
  title-style = color: black;  font-weight: bold; text-align: left;| 
  content-style = color: black;  text-align: left; |
}}

=== Комбінаторне доведення ===
{{Hider|
  title = Доведення. |
  hidden =1 |
  content =
Розглянемо довільний елемент <math>e \in U </math> і підрахуємо, скільки разів він враховується в правій частині формули включень-виключень<ref name = "Hall-2.1"/>.

Якщо елемент <math>e </math> не володіє жодною з властивостей <math>a_i </math>, то в правій частині формули він враховується рівно 1 раз (в члені <math>N</math>).

Нехай елемент <math>e</math> володіє рівно <math>r </math> властивостями <math>a_{j_1}, \ldots, a_{j_r}</math>. Тоді <math>e</math> дає по 1 в тих доданків суми 
<math> \sum \nolimits_ {i_1 <\ldots <i_s} N (a_{i_1}, \ldots, a_{i_s}) </math>, для яких <math> \{ i_1, \ldots, i_s \} </math> є підмножина <math> \{j_1, \ldots, j_r \} </math>,
і 0 для інших. Число таких підмножин за визначенням є [[Комбінація (комбінаторика)|число сполук]] <math> \tbinom {r} {s} </math>. Отже, внесок елемента <math>e</math> в праву частину дорівнює
<center>
<math> 1 - {r \choose 1} + {r \choose 2} - \ldots + (-1) ^n {r \choose n}. </math>
</center>
При <math>s> r </math> число сполучень дорівнює нулю. Сума, що залишилася в силу [[Біном Ньютона|біноміальної теореми]] дорівнює
<center>
<math> \sum_{s = 0} ^{r} (-1) ^s {r \choose s} = \bigg (1 + (- 1) \bigg) ^r = 0. </math>
</center>

Таким чином, права частина формули включень-виключень враховує кожен елемент, який не має зазначених властивостей точно по одному разу, а кожен елемент, що володіє хоча б однією з властивостей&nbsp;— нуль разів. Отже, вона дорівнює кількості елементів, що не володіють жодною з властивостей <math>a_i </math>, тобто <math> N (\overline {a} _1 \ldots \overline {a}_n) </math>. Що і потрібно було довести.
 |
  title-style = color: black;  font-weight: bold; text-align: left;| 
  content-style = color: black;  text-align: left; |
}}

=== Використовуючи індикаторні функції ===
{{Hider|
  title = Доведення. |
  hidden =1 |
  content =
Нехай <math>A_i </math>&nbsp;— ''довільні'' (не обов'язково скінченні) множини, які є підмножинами деякої множини <math>U</math>, і нехай <math> \mathbf {1}_{A_i} </math>&nbsp;— [[індикаторна функція|індикаторні функції]] <math>A_i </math> (або, еквівалентно, властивостей <math>a_i </math>).

Індикаторна функція їх [[Доповнення множин|доповнень]] <math>\overline {A_i} </math> дорівнює
<center>
<math> \mathbf {1} _ {\overline {A_i}} = 1 - \mathbf {1} _ {A_i}, </math>
</center>
а індикаторна функція [[Перетин множин|перетину]] доповнень:
<center>
<math> \mathbf {1} _ {\cap_ {i} \overline {A_i}} = \prod_ {i} (1 - \mathbf {1} _ {A_i}). </math>
</center>
Розкриваючи дужки в правій частині і ще раз використовуючи той факт, що індикаторна функція перетину множин дорівнює добутку їх індикаторних функцій, отримуємо:
<center>
<math> \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}. </math>
</center>
Це співвідношення&nbsp;— одна з форм принципу включень-виключень. Воно виражає собою логічну [[тотожність]]<ref name = "Riordan"/> і вірне для ''довільних'' множин <math> ~ A_i </math>. У разі скінченних множин <math>A_i </math> (і, відповідно, в припущенні скінченності множини <math>U </math>), якщо підсумувати це співвідношення по всіх <math>x \in U </math> і скористатися тим, що для довільного підмножини <math>A \subset U </math> його потужність дорівнює
<center>
<math> | A | = \sum_ {x \in U} \mathbf {1} _ {A} (x), </math> </center>
отримаємо формулювання принципу включень-виключень в термінах потужностей множин (або в термінах властивостей).
 |
  title-style = color: black;  font-weight: bold; text-align: left;| 
  content-style = color: black;  text-align: left; |
}}

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

=== Задача про безлад ===
{{Main|Безлад (перестановка)}}

Класичний приклад використання формули включень-виключень&nbsp;— задача про [[Безлад (перестановка)|безлад]]<ref name = "Hall-2.1"/>.
Потрібно знайти число [[Перестановка|перестановок]] <math> p_1, p_2, \ldots, p_n</math> множини <math>\{1, 2, \ldots, n \}</math> таких що <math> p_i \neq i </math> для всіх <math>i</math>. Такі перестановки називаються [[безлад]]ом.

Нехай <math>U </math>&nbsp;— [[множина]] всіх перестановок <math>p</math> і нехай властивість <math>a_i </math> перестановки виражається рівністю <math>p_i = i </math>. Тоді число безладів є <math> N (\overline {a}_1, \overline {a}_2, \ldots, \overline {a}_n) </math>. Легко бачити, що <math> N (a_{i_1}, \ldots, a_{i_s}) = (n-s)! </math>&nbsp;— число перестановок, що залишають на місці елементи <math> i_1, \ldots, i_s </math>, і таким чином сума <math> \sum N (a_{i_1}, a_{i_2}, \ldots, a_{i_s}) </math> містить <math> \tbinom {n} {s} </math> однакових доданків. Формула включень-виключень дає вираз для числа <math>D_n </math> безладів:
<center>
<math> D_n = n! - {N \choose 1} (n-1)! + {N \choose 2} (n-2)! - \ldots + (-1)^n {n \choose n} 0!. </math>
</center>
Це співвідношення можна перетворити до вигляду
<center>
<math> D_n = n! \left (1 - \frac {1} {1!} + \frac {1}{2!} - \ldots + \frac {(-1)^n} {n!} \right). </math>
</center>

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

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

{{Main|Функція Ейлера}}

Інший приклад застосування формули включень-виключень&nbsp;— знаходження явного вираження для [[Функція Ейлера|функції Ейлера]] <math> \varphi (n) </math><ref name = "Гнєденко"/>, що виражає кількість чисел з <math> 1, 2, \ldots, n,</math> [[Взаємно прості числа|взаємно простих]] з <math>n</math>.

Нехай [[Основна теорема арифметики|канонічне розкладання]] числа <math>n </math> на прості множники має вигляд
<center>
<math> n = p_1^{s_1} p_2^{s_2} \ldots p_k^{s_k}. </math>
</center>
Число <math>m \in 1, \ldots, n </math> взаємно просте з <math>n </math> тоді і тільки тоді, коли жоден з простих дільників <math>p_i </math> ділить <math>m </math>. Якщо тепер властивість <math>a_i </math> означає, що <math>p_i </math> ділить <math>m</math>, то кількість чисел, взаємно простих з <math>n </math> є <math>N (\overline {a} _1, \ldots, \overline {a}_k) </math>.

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

За формулою включень-виключень знаходимо:
<center>
<math> \varphi (n) = n - \sum_ {i} n / p_i + \sum_{i, j} n / p_i p_j - \ldots + (-1) ^ kn /p_1 \ldots p_k. </math> 
</center> 

Ця формула перетвориться до виду: 
<center> 
<math> \varphi (n) = n \prod_{i = 1}^{k} \left (1 - \frac{1} {p_i} \right). </math>
</center>

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

=== Принцип включення-виключення для ймовірностей ===
Нехай <math> (\Omega, \mathfrak {F}, \mathcal {P}) </math>&nbsp;— [[імовірнісний простір]]. Тоді для [[Випадкова подія|випадкових подій]] <math> A_1, A_2, \ldots, A_n </math> виконується формула<ref name = "Riordan"/>
<center> <math> 
\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). 
</math> </center>
Ця формула виражає принцип включень-виключень для [[Ймовірність|ймовірностей]]. Її можна отримати з принципу включень-виключень у формі індикаторних функцій:
<center>
<math> \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}. </math>
</center>

Нехай <math>A_i </math>&nbsp;— події імовірнісного простору <math> (\Omega, \mathfrak {F}, \mathcal {P}) </math>, тобто <math> A_i \in \mathfrak {F} </math>. Візьмемо [[математичне сподівання]] <math> \mathcal {M} </math> від обох частин цього співвідношення, і, скориставшись лінійністю математичного сподівання і рівністю <math> \mathcal {P} (A) = \mathcal {M} (\mathbf {1}_A) </math> для довільного події <math>A \in \mathfrak {F} </math>, отримаємо формулу включення-виключення для ймовірностей.

=== Принцип включень-виключень у просторах з мірою ===
Нехай <math> (X, \mathfrak {S}, \mu) </math>&nbsp;— [[простір з мірою]]. Тоді для довільних [[Вимірна множина|вимірних множин]] <math>A_i </math> кінцевої міри <math> \mu (A_i) <\infty </math> має місце формула включень-виключень:
<center>
<math> \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). </math>
</center>

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

Вивести принцип включень-виключень для просторів з мірою можна також, як для зазначених окремих випадків, з тотожності для індикаторних функцій:
<center>
<math> \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}. </math>
</center>

Нехай <math>A_i </math>&nbsp;— вимірні множини простору <math> (X, \mathfrak {S}, \mu) </math>, тобто <math>A_i \in \mathfrak {S} </math>. [[Інтеграл Лебега|Проінтегруємо]] обидві частини цієї рівності по [[Міра множини|мірі]] <math>\mu </math>, скористаємось [[Інтеграл Лебега|лінійністю інтеграла]] і співвідношенням <math> \mu ( A) = \int_{X} \mathbf {1}_A (x) \, d\mu </math>, і отримаємо формулу включень-виключень для міри.

=== Тотожність максимумів і мінімумів ===
{{Main | Тотожність максимумів і мінімумів}}
Формула включень-виключень може розглядатися як окремий випадок [[тотожність максимумів і мінімумів|тотожності максимумів і мінімумів]]:
<center> <math> 
\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). 
</math> </center>

Це співвідношення справедливо для довільних чисел <math>a_i </math>. В окремому випадку, коли <math>a_i \in \{0, 1 \} </math> ми отримуємо одну з форм принципу включень-виключень. Справді, якщо покласти <math>a_i = \mathbf {1}_{A_i} (x) </math>, де <math>x </math>&nbsp;— довільний елемент із <math>U </math>, то отримаємо співвідношення для індикаторних функцій множин:
<center>
<math> \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). </math>
</center>

=== Обертання Мебіуса ===
{{Main|Функція Мебіуса}}

Нехай <math>S </math>&nbsp;— кінцева множина, і нехай <math> f \colon 2^S \to \mathbb{R} </math>&nbsp;— довільна функція, визначена на сукупності підмножин <math>S</math>, яка приймає дійсні значення. Визначимо функцію <math> g \colon 2^S \to \mathbb{R} </math> наступним співвідношенням:
<center>
<math> g (Y) = \sum_{X \supset Y} f(X). </math>
</center>

Тоді має місце наступна формула звернення<ref name = "Hall-2.2"> {{книга 
| Автор = Холл М. 
| Заголовок = Комбінаторика 
| Оригінал = Combinatorial Theory 
| Місце = М. 
| Видавництво = «Мир» 
| Рік = 1970 
| Сторінки = 30-31 
| Сторінок = 424 
}} </ref>
<ref name = "Stanley"> {{книга 
| Автор = Стенлі Р. 
| Заголовок= Перечислительная комбинаторика 
| Оригінал = Enumerative Combinatorics 
| Місце = М. 
| Видавництво = «Мир» 
| Рік = 1990 
| Сторінки = 103-107 
| Сторінок = 440 
}} </ref>:
<center> <math> 
f (Y) = \sum_{X \supset Y} (-1)^{|X| - |Y|} \, g(X). 
</math> </center>

Це твердження є окремим випадком загальної [[Функція Мебіуса#Обертання Мебіуса|формули обертання Мебіуса]] для {{Нп |  Алгебра інцидентності |  алгебри інцидентності|  en| Incidence algebra }} сукупності <math>2^S </math> всіх підмножин множини <math>S </math>, [[Частково впорядкована множина|частково впорядкованих]] по [[Бінарне відношення|відношенню]] включення <math>\subset </math>.

Покажемо, як з цієї формули отримати принцип включення-виключення для скінченних множин.
Нехай дано сімейство підмножин <math> A_1, \ldots, A_n </math> скінченної множини <math>U </math>, позначимо <math> S = \{1, \ldots, n \} </math>&nbsp;— множина індексів. Для кожного набору індексів <math>X \subset S </math> визначимо <math>f (X) </math> як число елементів, що входять ''тільки'' в ті множини <math>A_i </math>, для яких <math>i \in X </math>. Математично це можна записати так:
<center>
<math> f (X) = \left | \left(\bigcap_{i \in X} A_i \right) \cap \left (\bigcap_{j \notin X} \overline {A_j} \right) \right|. </math>
</center>

Тоді функція <math>g \colon 2^S \to \mathbb{R} </math>, яка визначається формулою
<center> <math> 
g (Y) = \sum_{X \supset Y} f (X), 
</math> </center>
описує кількість елементів, кожний з яких входить у всі множини <math>A_i </math>, <math>i \in X </math> і, бути може, ще в інші. Тобто
<center> <math> 
g (X) = \left| \bigcap_{i \in X} A_i \right|. 
</math> </center>

Зауважимо далі, що <math>f (\varnothing) </math>&nbsp;— кількість елементів, що не володіють жодною з властивостей:
<center> <math> 
f (\varnothing) = \left | \bigcap_{i} \overline {A_i} \right |. 
</math> </center>

З урахуванням зроблених зауважень запишемо формулу обернення Мебіуса:
<center> <math> 
\left| \bigcap_ {i} \overline {A_i} \right| = \sum_{X} (-1)^{|X|} \, \left| \bigcap_{i \ in X} A_i \right|. 
</math> </center>
Це є в точності формула включень-виключень для скінченних множин, тільки в ній не згруповані доданки, пов'язані з однаковим значенням <math>| X | </math>.

== Див. також ==
* [[Формула Грассмана]]
* {{Нп|Нерівність Буля|||Boole's inequality}}

== Примітки ==
{{Примітки|2}}

== Посилання ==
* {{Вишенський.Перестюк.Комбінаторика}}
* {{MathWorld|urlname=Inclusion-ExclusionPrinciple|title=Формула включень-виключень}}

[[Категорія:Нумераційна комбінаторика]]
[[Категорія:Теорія множин]]
[[Категорія:Теорія ймовірностей]]
[[Категорія:Математичні принципи]]