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

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

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

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

${\displaystyle |A\cup B|=|A|+|B|-|A\cap B|.}$

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

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

У випадку трьох множин A, B та C формула має вигляд:

${\displaystyle |A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|.}$

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

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

Історія

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle N(0)=\sum _{k=0}^{n}(-1)^{k}\sum _{i_{1}<\ldots <i_{k}}N(i_{1},\ldots ,i_{k}).}$

Доведення

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

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

Доведення за математичною індукцією.  

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

При ${\displaystyle n=1}$ формула включень-виключень тривіальна:

${\displaystyle N({\overline {a}})=N-N(a).}$

Нехай формула вірна для ${\displaystyle n=m}$, доведемо її для ${\displaystyle n=m+1}$.

Нехай кожен елемент множини ${\displaystyle U}$ може володіти або мати будь-яку з властивостей ${\displaystyle a_{1},\ldots ,a_{m},a_{m+1}}$. Застосуємо формулу включень-виключень для властивостей ${\displaystyle a_{1},\ldots ,a_{m}}$:

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

Тепер застосуємо формулу для властивостей ${\displaystyle a_{1},\ldots ,a_{m}}$ до множини ${\displaystyle N(a_{m+1})}$ об'єктів, для яких виконано властивість ${\displaystyle a_{m+1}}$:

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

Нарешті, застосуємо формулу для однієї властивості ${\displaystyle a_{m+1}}$ до сукупності ${\displaystyle N({\overline {a}}_{1}\ldots {\overline {a}}_{m})}$, об'єктів, які не володіють властивостями ${\displaystyle a_{1},\ldots ,a_{m}}$:

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

Комбінуючи виписані три формули, отримаємо формулу включень-виключень для ${\displaystyle m+1}$ властивостей ${\displaystyle a_{1},\ldots ,a_{m+1}}$. Що і потрібно було довести.

Комбінаторне доведення

Доведення.  

Розглянемо довільний елемент ${\displaystyle e\in U}$ і підрахуємо, скільки разів він враховується в правій частині формули включень-виключень.

Якщо елемент ${\displaystyle e}$ не володіє жодною з властивостей ${\displaystyle a_{i}}$, то в правій частині формули він враховується рівно 1 раз (в члені ${\displaystyle N}$).

Нехай елемент ${\displaystyle e}$ володіє рівно ${\displaystyle r}$ властивостями ${\displaystyle a_{j_{1}},\ldots ,a_{j_{r}}}$. Тоді ${\displaystyle e}$ дає по 1 в тих доданків суми ${\displaystyle \sum \nolimits _{i_{1}<\ldots <i_{s}}N(a_{i_{1}},\ldots ,a_{i_{s}})}$, для яких ${\displaystyle \{i_{1},\ldots ,i_{s}\}}$ є підмножина ${\displaystyle \{j_{1},\ldots ,j_{r}\}}$, і 0 для інших. Число таких підмножин за визначенням є число сполук ${\displaystyle {\tbinom {r}{s}}}$. Отже, внесок елемента ${\displaystyle e}$ в праву частину дорівнює

${\displaystyle 1-{r \choose 1}+{r \choose 2}-\ldots +(-1)^{n}{r \choose n}.}$

При ${\displaystyle s>r}$ число сполучень дорівнює нулю. Сума, що залишилася в силу біноміальної теореми дорівнює

${\displaystyle \sum _{s=0}^{r}(-1)^{s}{r \choose s}={\bigg (}1+(-1){\bigg )}^{r}=0.}$

Таким чином, права частина формули включень-виключень враховує кожен елемент, який не має зазначених властивостей точно по одному разу, а кожен елемент, що володіє хоча б однією з властивостей — нуль разів. Отже, вона дорівнює кількості елементів, що не володіють жодною з властивостей ${\displaystyle a_{i}}$, тобто ${\displaystyle N({\overline {a}}_{1}\ldots {\overline {a}}_{n})}$. Що і потрібно було довести.

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

Доведення.  

Нехай ${\displaystyle A_{i}}$ — довільні (не обов'язково скінченні) множини, які є підмножинами деякої множини ${\displaystyle U}$, і нехай ${\displaystyle \mathbf {1} _{A_{i}}}$ — (індикаторні функції) ${\displaystyle A_{i}}$ (або, еквівалентно, властивостей ${\displaystyle a_{i}}$).

Індикаторна функція їх доповнень ${\displaystyle {\overline {A_{i}}}}$ дорівнює

${\displaystyle \mathbf {1} _{\overline {A_{i}}}=1-\mathbf {1} _{A_{i}},}$

а індикаторна функція перетину доповнень:

${\displaystyle \mathbf {1} _{\cap _{i}{\overline {A_{i}}}}=\prod _{i}(1-\mathbf {1} _{A_{i}}).}$

Розкриваючи дужки в правій частині і ще раз використовуючи той факт, що індикаторна функція перетину множин дорівнює добутку їх індикаторних функцій, отримуємо:

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

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

${\displaystyle |A|=\sum _{x\in U}\mathbf {1} _{A}(x),}$

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

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

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

Докладніше: Безлад (перестановка)

Класичний приклад використання формули включень-виключень — задача про безлад. Потрібно знайти число перестановок ${\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 D_{n}=n!-{N \choose 1}(n-1)!+{N \choose 2}(n-2)!-\ldots +(-1)^{n}{n \choose n}0!.}$

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

${\displaystyle D_{n}=n!\left(1-{\frac {1}{1!}}+{\frac {1}{2!}}-\ldots +{\frac {(-1)^{n}}{n!}}\right).}$

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

${\displaystyle D_{n}/P_{n}\approx 1/e.}$

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

Докладніше: Функція Ейлера

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

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

${\displaystyle n=p_{1}^{s_{1}}p_{2}^{s_{2}}\ldots p_{k}^{s_{k}}.}$

Число ${\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 \varphi (n)=n-\sum _{i}n/p_{i}+\sum _{i,j}n/p_{i}p_{j}-\ldots +(-1)^{k}n/p_{1}\ldots p_{k}.}$

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

${\displaystyle \varphi (n)=n\prod _{i=1}^{k}\left(1-{\frac {1}{p_{i}}}\right).}$

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

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

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

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

Нехай ${\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 {\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).}$

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

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

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

Нехай ${\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 \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).}$

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

Докладніше: Функція Мебіуса

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

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

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

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

Це твердження є окремим випадком загальної формули обертання Мебіуса для ^[en] сукупності ${\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 f(X)=\left|\left(\bigcap _{i\in X}A_{i}\right)\cap \left(\bigcap _{j\notin X}{\overline {A_{j}}}\right)\right|.}$

Тоді функція ${\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|}$.

Див. також

• ^[en]

Примітки

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

Посилання

• И. Яглом. Заплаты на кафтане // Квант. — 1974. — № 2. — С. 13—21.
• Weisstein, Eric W. Inclusion-Exclusion Principle(англ.) на сайті Wolfram MathWorld.