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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Випадок двох множин

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

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

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

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

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

У випадку трьох множин A, B and 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 році[1]. Але ще в 1713 Микола Бернуллі (англ.) використовував цей метод для вирішення завдання Монмора (англ.), відомої як задача про зустрічі[ru] (фр. Le problème des rencontres)[2], окремим випадком якої є завдання про безлад[en]. Також формулу включень-виключень пов'язують з іменами французького математика Абрахама де Муавра і англійського математика Джозефа Сильвестра[3]. У теорії ймовірностей аналог принципу включень-виключень відомий як формула Анрі Пуанкаре[4].

Формулювання[ред.ред. код]

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

У термінах множин[ред.ред. код]

Нехай  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 отримуємо формули для двох або трьох множин, наведені вище.

У термінах властивостей[ред.ред. код]

Принцип включень-виключень часто наводять в такому альтернативному формулюванні [5]. Нехай дано кінцеву множину 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).

Доведення[ред.ред. код]

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

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

Комбінаторне доведення[ред.ред. код]

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

Застосування[ред.ред. код]

Задача про безлад[ред.ред. код]

Докладніше: Безлад

Класичний приклад використання формули включень-виключень — завдання про безлад[en][5]. Потрібно знайти число перестановок  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}) = (ns)!  — число перестановок, що залишають на місці елементи  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) [7], що виражає кількість чисел з  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) ^ kn /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 виконується формула[1][6][8]

 
\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 , і отримаємо формулу включень-виключень для міри.

Тотожність максимумів і мінімумів[ред.ред. код]

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

 
\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).

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

 
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 \ in X} A_i \right|.

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

Див. також[ред.ред. код]

Примітки[ред.ред. код]

  1. а б в г Ріордан Дж. Введення в комбінаторний аналіз = An Introduction to Combinatorial Analysis. — 289 с.
  2. Weisstein, Eric W. Derangement(англ.) на сайті Wolfram MathWorld.
  3. Рибніков К. А. Введення в комбінаторний аналіз. — 2-е вид. — 309 с.
  4. Ріордан Дж. Введення в комбінаторний аналіз = An Introduction to Combinatorial Analysis. — М.: Вид-во іноземної літератури, 1963. — 289 с.
  5. а б в Холл М. Комбінаторика = Combinatorial Theory. — 424 с.
  6. а б Рибніков К. А. Введення в комбінаторний аналіз. — 2-е вид. — 309 с.
  7. Рибніков К. А. Введення в комбінаторний аналіз. — 2-е вид. — 309 с.
  8. Боровков, А. А. Теорія ймовірностей. — 2-е вид. — 431 с.
  9. Холл М. Комбінаторика = Combinatorial Theory. — 424 с.
  10. Стенлі Р. Перечислительная комбинаторика = Enumerative Combinatorics. — 440 с.

Посилання[ред.ред. код]