Zasada włączeń i wyłączeń

Zasada włączeń i wyłączeń – reguła kombinatoryczna, pozwalająca na określenie liczby elementów skończonej sumy mnogościowej skończonych zbiorów. Autorstwo zasady przypisywane jest zazwyczaj Abrahamowi de Moivre, chociaż bywa nazywana od nazwisk matematyków, Jamesa Josepha Sylvestera oraz Henriego Poincaré.

Twierdzenie

Niech $A_{1}, A_{2} \dots A_{n}$ będą dowolnymi skończonymi zbiorami zaś $i, j, k \in {1, \dots, n} .$ Wówczas

\begin{matrix} | ⋃_{i = 1}^{n} A_{i} | & = \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 + (- 1)^{n - 1} | A_{1} \cap \dots \cap A_{n} |, \end{matrix}

gdzie $| A_{k} |$ oznacza moc zbioru $A_{k} .$

Przykład

Dla trzech zbiorów skończonych $A_{1}, A_{2}, A_{3}$ liczba elementów ich sumy wyraża się wzorem:

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

Wzór zapewnia, że elementy znajdujące się jednocześnie w kilku spośród zbiorów $A_{1}, A_{2}, \dots, A_{n}$ liczone są dokładnie raz.

Dowód

Niech element $a$ należy dokładnie do $m$ spośród zbiorów $A_{1}, A_{2} \dots A_{n} .$ W sumie mnogościowej $⋃_{i = 1}^{n} A_{i}$ ma on być liczony tylko jeden raz. W wyrażeniu

\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

\dots + (- 1)^{n - 1} | A_{1} \cap \dots \cap A_{n} |

liczba zliczeń pojedynczego elementu jest równa:

\begin{matrix} m & - (\binom{m}{2}) + (\binom{m}{3}) + \dots + (- 1)^{m} (\binom{m}{m - 1}) + (- 1)^{m + 1} 1 \\ = 1 & - (\binom{m}{0}) + (\binom{m}{1}) + \dots + (- 1)^{m} (\binom{m}{m - 1}) + (- 1)^{m + 1} (\binom{m}{m}), \end{matrix}

bowiem występuje on w $m$ zbiorach spośród $A_{1}, A_{2} \dots A_{n},$ $(\binom{m}{2})$ zbiorach spośród $A_{i} \cap A_{j}, 1 ⩽ i < j ⩽ n$ itd.

Na mocy rozwinięcia Newtona wyrażenie to jest równe $1 - (1 - 1)^{m} = 1 - 0 = 1,$ 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ń mierzalną $(X, Σ, μ) .$ Wtedy, twierdzenie przyjmuje postać:

Niech dana będzie przestrzeń mierzalna $(X, Σ, μ) .$ Dla dowolnych zbiorów mierzalnych (tj. należących do $σ$ -algebry $Σ$ ) o skończonej mierze $A_{1}, A_{2} \dots A_{n}$ zachodzi

\begin{matrix} μ (⋃_{i = 1}^{n} A_{i}) & = \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 + (- 1)^{n - 1} μ (A_{1} \cap \dots \cap A_{n}) . \end{matrix}

W szczególności, podana wcześniej moc zbioru jest miarą liczącą.

W 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ń $A_{1}, A_{2} \dots A_{n}$ wzór ten przyjmuje postać

ℙ (A_{1} \cup A_{2}) = ℙ (A_{1}) + ℙ (A_{2}) - ℙ (A_{1} \cap A_{2})

i ogólnie

\begin{matrix} ℙ (⋃_{i = 1}^{n} A_{i}) & = \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 + (- 1)^{n - 1} ℙ (A_{1} \cap \dots \cap A_{n}), \end{matrix}

gdzie $ℙ$ jest prawdopodobieństwem, określonym w danym eksperymencie losowym (przestrzeni probabilistycznej).

Bibliografia

Linki zewnętrzne

Szablon:Pismo Delta
Szablon:MathWorld [dostęp 2024-03-07].

Szablon:Kombinatoryka

Szablon:Kontrola autorytatywna

Zasada włączeń i wyłączeń

Spis treści

Twierdzenie

Przykład

Dowód

Uogólnienia

Bibliografia

Linki zewnętrzne

Menu nawigacyjne

Zasada włączeń i wyłączeń

Twierdzenie

Przykład

Dowód

Uogólnienia

Bibliografia

Linki zewnętrzne

Menu nawigacyjne

Szukaj