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

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj
Niniejszy artykuł jest częścią cyklu kombinatoryka.




permutacja


kombinacja bez powtórzeń
kombinacja z powtórzeniami


wariacja bez powtórzeń
wariacja z powtórzeniami


liczby Bella
liczby Catalana
liczby Stirlinga
liczby Eulera


zasada szufladkowa Dirichleta
zasada włączeń i wyłączeń


Zasada właczeń i wyłączeń, pokazana dla trzech zbiorów

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[edytuj | edytuj kod]

Niech A_1, A_2 \dots A_n będą dowolnymi skończonymi zbiorami zaś i, j, k \in \{1, \ldots, n\}. Wówczas

\left|\bigcup_{i=1}^n A_i\right|=\sum_{i=1}^n\left|A_i\right|
-\sum_{i,j:\,i<j}\left|A_i\cap A_j\right| +
+ \sum_{i,j,k:\,i<j<k}\left|A_i\cap A_j\cap A_k\right|-\ \dots  + (-1)^{n-1} \left|A_1\cap\cdots\cap A_n\right|,

gdzie \left|A_k\right| oznacza moc zbioru A_k \,

Przykład[edytuj | edytuj kod]

Dla trzech zbiorów skończonych A_1, A_2, A_3 liczba elementów ich sumy wyraża się wzorem:

\left|A_1 \cup A_2 \cup A_3 \right| = \left|A_1 \right| + \left|A_2\right| + \left|A_3 \right| - \left|A_1 \cap A_2 \right| - \left|A_1 \cap A_3 \right| -\left| A_2 \cap A_3 \right| + \left|A_1 \cap A_2 \cap A_3 \right|

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[edytuj | edytuj kod]

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 \bigcup_{i=1}^n A_i jest on liczony jeden raz. W wyrażeniu

\sum_{i=1}^n\left|A_i\right|
-\sum_{i,j:\,i < j}\left|A_i\cap A_j\right| +\sum_{i,j,k:\,i<j<k}\left|A_i\cap A_j\cap A_k\right|-\ \dots
 \ \dots + (-1)^{n-1} \left|A_1\cap\cdots\cap A_n\right|

liczba zliczeń pojedynczego elementu jest równa:

m - {m \choose 2} + {m \choose 3} + \dots + (-1)^m  {m \choose {m-1}} + (-1)^{m+1}  1 =
= 1 - {m \choose 0} + {m \choose 1} + \dots + (-1)^m {m \choose {m-1}}  + (-1)^{m+1} {m \choose m},

bowiem występuje on w m zbiorach spośród A_1, A_2 \dots A_n, {m \choose 2} zbiorach spośród A_i\cap A_j, 1 \le i < j \le 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 jeden raz.

Uogólnienia[edytuj | edytuj kod]

Zasada włączeń i wyłączeń pozostaje prawdziwa, gdy nasze rozważania przeniesiemy na dowolną przestrzeń z miarą (X,\Sigma,\mu). Wtedy, twierdzenie przyjmuje postać:

Niech dana będzie przestrzeń z miarą (X,\Sigma,\mu). Dla dowolnych zbiorów mierzalnych (tj. należących do \sigma-algebry \Sigma) o skończonej mierze A_1, A_2 \dots A_n zachodzi

\mu\left(\bigcup_{i=1}^n A_i\right)=\sum_{i=1}^n\mu\left(A_i\right)
-\sum_{i,j:\,i<j}\mu\left(A_i\cap A_j\right) +
+ \sum_{i,j,k:\,i<j<k}\mu\left(A_i\cap A_j\cap A_k\right)-\ \dots  + (-1)^{n-1} \mu\left(A_1\cap\cdots\cap A_n\right).

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ć

\mathbb{P}(A_1\cup A_2)=\mathbb{P}(A_1)+\mathbb{P}(A_2)-\mathbb{P}(A_1\cap A_2)

i ogólnie,

\mathbb{P}\left(\bigcup_{i=1}^n A_i\right)=\sum_{i=1}^n\mathbb{P}\left(A_i\right)
-\sum_{i,j:\,i<j}\mathbb{P}\left(A_i\cap A_j\right) +
+ \sum_{i,j,k:\,i<j<k}\mathbb{P}\left(A_i\cap A_j\cap A_k\right)-\ \dots  + (-1)^{n-1} \mathbb{P}\left(A_1\cap\cdots\cap A_n\right),

gdzie \mathbb{P} jest prawdopodobieństwem, określonym w danym eksperymencie losowym (przestrzeni probabilistycznej).

Bibliografia[edytuj | edytuj kod]

  • Jacek Jakubowski, Rafał Sztencel: Wstęp do teorii prawdopodobieństwa. Warszawa: SCRIPT, 2001, s. 11-12.
  • Zbigniew Bobiński, Lev Kourliandtchik, Mirosław Uscki: Miniatury matematyczne. Elementarne metody w kombinatoryce. Toruń: Wydawnictwo Aksjomat, 2002, s. 11-15. ISBN 83-87329-35-5.