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

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

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

Наприклад, у випадку двох множин $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 \dots \cup A_n$ полягає у включенні всього, потім виключення зайвого, потім включенні помилково виключеного і так далі, тобто в чергуванні включення і виключення. Звідси і походить назва формули.

Історія

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

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

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

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

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

$\left|\bigcup _{i=1}^n{A}_i\right|=\sum _{i=1}^n\left|A_i\right|-\sum _{1⩽i<j⩽n}|A_i\cap A_j|+\sum _{1⩽i<j<k⩽n}|A_i\cap A_j\cap A_k|-\dots +{(-1)}^{n-1}|A_1\cap \cdots \cap A_n|.$

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

$\left|\bigcup _{i=1}^n{A}_i\right|=\sum _{k=1}^n(-1{)}^{k+1}\left(\sum _{1⩽i_1<\cdots <i_k⩽n}|A_{i_1}\cap \cdots \cap A_{i_k}|\right)$

або

$\left|\bigcup _{i=1}^n{A}_i\right|=\sum _{\mathrm{\varnothing }\ne J\subseteq \{1,2,\dots ,n\}}(-1{)}^{|J|-1}|\bigcap _{j\in J}{A}_j|.$

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

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

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

$N({\bar{a}}_1\dots {\bar{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)+\dots +(-1{)}^{n}N(a_1\dots a_n).$

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

$\left|\bigcap _{i=1}^n\overline{A_i}\right|=|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|+\dots +(-1{)}^n|A_1\cap A_2\cap \dots \cap A_n|.$

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

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

$N(0)=\sum _{k=0}^n(-1{)}^k\sum _{i_1<\dots <i_k}N(i_1,\dots ,i_k).$

Доведення

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

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

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

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

Нехай $U$ — множина всіх перестановок $p$ і нехай властивість $a_i$ перестановки виражається рівністю $p_i=i$. Тоді число безладів є $N({\bar{a}}_1,{\bar{a}}_2,\dots ,{\bar{a}}_n)$. Легко бачити, що $N(a_{i_1},\dots ,a_{i_s})=(n-s)!$ — число перестановок, що залишають на місці елементи $i_1,\dots ,i_s$, і таким чином сума $\sum N(a_{i_1},a_{i_2},\dots ,a_{i_s})$ містить $(\genfrac{}{}{0ex}{}{n}{s})$ однакових доданків. Формула включень-виключень дає вираз для числа $D_n$ безладів:

$D_n=n!-(\genfrac{}{}{0ex}{}{N}{1})(n-1)!+(\genfrac{}{}{0ex}{}{N}{2})(n-2)!-\dots +(-1{)}^n(\genfrac{}{}{0ex}{}{n}{n})0!.$

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

$D_n=n!(1-\frac{1}{1!}+\frac{1}{2!}-\dots +\frac{(-1{)}^n}{n!}).$

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

$D_n/P_n\approx 1/e.$

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

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

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

$n=p_1^{s_1}{p}_2^{s_2}\dots p_k^{s_k}.$

Число $m\in 1,\dots ,n$ взаємно просте з $n$ тоді і тільки тоді, коли жоден з простих дільників $p_i$ ділить $m$. Якщо тепер властивість $a_i$ означає, що $p_i$ ділить $m$, то кількість чисел, взаємно простих з $n$ є $N({\bar{a}}_1,\dots ,{\bar{a}}_k)$.

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

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

$\phi (n)=n-\sum _{i}n/p_i+\sum _{i,j}n/p_i{p}_j-\dots +(-1{)}^{k}n/p_1\dots p_k.$

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

$\phi (n)=n\prod _{i=1}^k(1-\frac{1}{p_i}).$

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

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

Нехай $(\mathrm{\Omega },𝔉,𝒫)$ — імовірнісний простір. Тоді для випадкових подій $A_1,A_2,\dots ,A_n$ виконується формула

$𝒫\left(\bigcup _{i=1}^n{A}_i\right)=\sum _i𝒫(A_i)-\sum _{i<j}𝒫(A_i\cap A_j)+\sum _{i<j<k}𝒫(A_i\cap A_j\cap A_k)+\dots +(-1{)}^{n-1}𝒫\left(\bigcap _{i=1}^n{A}_i\right).$

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

${\mathrm{𝟏}}_{\bigcup _i{A}_i}=\sum _i{\mathrm{𝟏}}_{A_i}-\sum _{i<j}{\mathrm{𝟏}}_{A_i\cap A_j}+\sum _{i<j<k}{\mathrm{𝟏}}_{A_i\cap A_j\cap A_k}+\dots +(-1{)}^{n-1}{\mathrm{𝟏}}_{A_1\cap \dots \cap A_n}.$

Нехай $A_i$ — події імовірнісного простору $(\mathrm{\Omega },𝔉,𝒫)$, тобто $A_i\in 𝔉$. Візьмемо математичне сподівання $ℳ$ від обох частин цього співвідношення, і, скориставшись лінійністю математичного сподівання і рівністю $𝒫(A)=ℳ({\mathrm{𝟏}}_A)$ для довільного події $A\in 𝔉$, отримаємо формулу включення-виключення для ймовірностей.

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

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

$\mu \left(\bigcup _{i=1}^n{A}_i\right)=\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)+\dots +(-1{)}^{n-1}\mu \left(\bigcap _{i=1}^n{A}_i\right).$

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

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

${\mathrm{𝟏}}_{\bigcup _i{A}_i}=\sum _i{\mathrm{𝟏}}_{A_i}-\sum _{i<j}{\mathrm{𝟏}}_{A_i\cap A_j}+\sum _{i<j<k}{\mathrm{𝟏}}_{A_i\cap A_j\cap A_k}+\dots +(-1{)}^{n-1}{\mathrm{𝟏}}_{A_1\cap \dots \cap A_n}.$

Нехай $A_i$ — вимірні множини простору $(X,𝔖,\mu )$, тобто $A_i\in 𝔖$. Проінтегруємо обидві частини цієї рівності по мірі $\mu$, скористаємось лінійністю інтеграла і співвідношенням $\mu (A)=\underset{X}{\int }{\mathrm{𝟏}}_A(x)d\mu$, і отримаємо формулу включень-виключень для міри.

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

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

$\max (a_1,\dots ,a_n)=\sum _i{a}_i-\sum _{i<j}\min (a_i,a_j)+\dots +(-1{)}^{n-1}\min (a_1,\dots ,a_n).$

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

${\mathrm{𝟏}}_{\bigcup _i{A}_i}(x)=\sum _i{\mathrm{𝟏}}_{A_i}(x)-\sum _{i<j}{\mathrm{𝟏}}_{A_i\cap A_j}(x)+\sum _{i<j<k}{\mathrm{𝟏}}_{A_i\cap A_j\cap A_k}(x)+\dots +(-1{)}^{n-1}{\mathrm{𝟏}}_{A_1\cap \dots \cap A_n}(x).$

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

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

$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,\dots ,A_n$ скінченної множини $U$, позначимо $S=\{1,\dots ,n\}$ — множина індексів. Для кожного набору індексів $X\subset S$ визначимо $f(X)$ як число елементів, що входять тільки в ті множини $A_i$, для яких $i\in X$. Математично це можна записати так:

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

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

$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 _{iinX}{A}_i\right|.$

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

Див. також

• Формула Грассмана
• Шаблон:Нп

Посилання

• Шаблон:Вишенський.Перестюк.Комбінаторика
• Шаблон:MathWorld