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

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

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

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

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

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

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

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

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

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

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

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

Нехай  A_1, A_2, \ldots, A_n  — скінченні множини. Формула включень-виключень стверджує:

 \biggl | \bigcup_ {i = 1} ^ {n} A_i \biggl | = \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-1} | A_1 \cap A_2 \cap \ldots \cap A_n |.

При 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).

Доказ[ред.ред. код]

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

За індукції[ред.ред. код]

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

При  ~ 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 \leq m} N (a_i) + \sum_ {i <j \leq 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 \leq m} N (a_i a_ { m +1}) + \sum_ {i <j \ leq 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 і підрахуємо, скільки разів він враховується в правій частині формули включень-виключень[5].

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

Нехай елемент  ~ \ e має в точності  ~ r властивостями, скажімо  ~ a_ {j_1}, \ldots, a_ {j_r} . Він дає по 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}.

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

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

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

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

Задача про заворушення[ред.ред. код]

Класичний приклад використання формули включень-виключень — завдання про заворушення[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 , і отримаємо формулу включень-виключень для міри.

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

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

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

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