Tekst źródłowy strony Zasada włączeń i wyłączeń

[[Plik:Inclusion-exclusion.svg|thumb|Zasada włączeń i wyłączeń, pokazana dla trzech zbiorów]]
'''Zasada włączeń i wyłączeń''' – reguła [[kombinatoryka|kombinatoryczna]], pozwalająca na określenie liczby elementów skończonej [[suma zbiorów|sumy mnogościowej]] [[zbiór skończony|skończonych]] [[zbiór|zbiorów]]. Autorstwo zasady przypisywane jest zazwyczaj [[Abraham de Moivre|Abrahamowi de Moivre]], chociaż bywa nazywana od nazwisk matematyków, [[James Joseph Sylvester|Jamesa Josepha Sylvestera]] oraz [[Henri Poincaré|Henriego Poincaré]].

== Twierdzenie ==
Niech <math>A_1, A_2 \dots A_n</math> będą dowolnymi skończonymi zbiorami zaś <math>i, j, k \in \{1, \dots, n\}.</math> Wówczas
: <math>\begin{align}
 \left|\bigcup_{i=1}^n A_i\right| &= \sum_{i=1}^n |A_i|
-\sum_{i,j:\,i<j} |A_i\cap A_j| \\
&+ \sum_{i,j,k:\,i<j<k} |A_i\cap A_j\cap A_k| - \ldots + (-1)^{n-1} |A_1\cap\ldots\cap A_n|,
\end{align}</math>

gdzie <math>|A_k|</math> oznacza [[moc zbioru]] <math>A_k.</math>

=== Przykład ===
Dla trzech zbiorów skończonych <math>A_1, A_2, A_3</math> liczba elementów ich sumy wyraża się wzorem:
: <math>|A_1 \cup A_2 \cup A_3| = |A_1| + |A_2| + |A_3| - |A_1 \cap A_2| - |A_1 \cap A_3| - |A_2 \cap A_3| + |A_1 \cap A_2 \cap A_3|.</math>

Wzór zapewnia, że elementy znajdujące się jednocześnie w kilku spośród zbiorów <math>A_1, A_2, \dots, A_n</math> liczone są dokładnie raz.

== Dowód ==
Niech element <math>a</math> należy dokładnie do <math>m</math> spośród zbiorów <math>A_1, A_2 \dots A_n.</math> W sumie mnogościowej <math>\bigcup_{i=1}^n A_i</math> ma on być liczony tylko jeden raz. W wyrażeniu
: <math>\sum_{i=1}^n |A_i|
-\sum_{i,j:\,i < j} |A_i\cap A_j| + \sum_{i,j,k:\,i<j<k} |A_i\cap A_j\cap A_k| - \dots</math>
: <math>\ldots + (-1)^{n-1} |A_1\cap\ldots\cap A_n|</math>

liczba zliczeń pojedynczego elementu jest równa:
: <math>\begin{align}
m &- {m \choose 2} + {m \choose 3} + \ldots + (-1)^m {m \choose {m-1}} + (-1)^{m+1} 1 \\
= 1 &- {m \choose 0} + {m \choose 1} + \ldots + (-1)^m {m \choose {m-1}} + (-1)^{m+1} {m \choose m},
\end{align}</math>

bowiem występuje on w <math>m</math> zbiorach spośród <math>A_1, A_2 \dots A_n,</math> <math>m \choose 2</math> zbiorach spośród <math>A_i\cap A_j, 1 \leqslant i < j \leqslant n</math> itd.

Na mocy [[dwumian Newtona|rozwinięcia Newtona]] wyrażenie to jest równe <math>1 - (1-1)^m = 1-0 = 1,</math> co dowodzi poprawności zasady włączeń i wyłączeń, bowiem element został policzony tylko jeden raz.

== Uogólnienia ==
Zasada włączeń i wyłączeń pozostaje prawdziwa, gdy nasze rozważania przeniesiemy na dowolną [[przestrzeń mierzalna|przestrzeń mierzalną]] <math>(X,\Sigma,\mu).</math> Wtedy, twierdzenie przyjmuje postać:

Niech dana będzie przestrzeń mierzalna <math>(X,\Sigma,\mu).</math> Dla dowolnych zbiorów mierzalnych (tj. należących do [[Przestrzeń mierzalna|<math>\sigma</math>-algebry]] <math>\Sigma</math>) o skończonej mierze <math>A_1, A_2 \dots A_n</math> zachodzi
: <math>\begin{align}
\mu \left(\bigcup_{i=1}^n A_i\right) &=\sum_{i=1}^n\mu (A_i) - \sum_{i,j:\,i<j} \mu (A_i\cap A_j) \\
&+ \sum_{i,j,k:\,i<j<k} \mu (A_i\cap A_j\cap A_k) - \ldots + (-1)^{n-1} \mu (A_1\cap\ldots\cap A_n).
\end{align}</math>

W szczególności, podana wcześniej moc zbioru jest [[miara licząca|miarą liczącą]].

W [[Teoria prawdopodobieństwa|teorii prawdopodobieństwa]], gdzie rozważa się przestrzenie zdarzeń elementarnych, wraz z określonymi nań miarami probabilistycznymi, zwanymi prawdopodobieństwami, wzór włączeń-wyłączeń odgrywa rolę przy liczeniu prawdopodobieństwa zajścia odpowiednich zdarzeń. Dla dowolnych zdarzeń <math>A_1, A_2 \dots A_n</math> wzór ten przyjmuje postać
: <math>\mathbb{P}(A_1\cup A_2) = \mathbb{P}(A_1)+\mathbb{P}(A_2)-\mathbb{P}(A_1\cap A_2)</math>

i ogólnie
: <math>\begin{align}
\mathbb{P} \left(\bigcup_{i=1}^n A_i\right) &= \sum_{i=1}^n\mathbb{P} (A_i)
-\sum_{i,j:\,i<j}\mathbb{P} (A_i\cap A_j) \\
&+ \sum_{i,j,k:\,i<j<k}\mathbb{P} (A_i\cap A_j\cap A_k) - \ldots + (-1)^{n-1} \mathbb{P} (A_1\cap\ldots\cap A_n),
\end{align}</math>

gdzie <math>\mathbb{P}</math> jest prawdopodobieństwem, określonym w danym eksperymencie losowym ([[przestrzeń probabilistyczna|przestrzeni probabilistycznej]]).

== Bibliografia ==
* {{cytuj książkę |nazwisko = Jakubowski |imię = Jacek |nazwisko2 = Sztencel |imię2 = Rafał |tytuł = Wstęp do teorii prawdopodobieństwa |miejsce = Warszawa |rok = 2001 |wydawca = SCRIPT |strony = 11–12 |odn = tak}}
* {{cytuj książkę |nazwisko = Bobiński |imię = Zbigniew |nazwisko2 = Kourliandtchik |imię2 = Lev |nazwisko3 = Uscki |imię3 = Mirosław |tytuł = Miniatury matematyczne. Elementarne metody w kombinatoryce |wydawca = Wydawnictwo Aksjomat |miejsce = Toruń |strony = 11–15 |rok = 2002 |isbn = 83-87329-35-5 |odn = tak}}

== Linki zewnętrzne ==
* {{Pismo Delta |url = 2022a/07/2022-07-delta-art-15-kpo.pdf |autor = Bartłomiej Bzdęga |tytuł = Reguła włączeń i wyłączeń |data = lipiec 2022 |data dostępu = 2022-07-02}}
* {{MathWorld | adres = Inclusion-ExclusionPrinciple | tytuł = Inclusion-Exclusion Principle }} [dostęp 2024-03-07].

{{Kombinatoryka}}

{{Kontrola autorytatywna}}

[[Kategoria:Twierdzenia teorii miary]]
[[Kategoria:Twierdzenia probabilistyki]]
[[Kategoria:Twierdzenia kombinatoryki]]