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

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

${\displaystyle {\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|.}$

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

${\displaystyle {\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)}$

або

${\displaystyle {\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 |}.}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle {\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).}$

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

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

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

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

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

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

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

${\displaystyle \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}).}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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