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

Z Wikipedii

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ń

Ten szablon: pokaż • dyskusja • edytuj

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

[edytuj] Twierdzenie

Niech $A_1, A_2 \dots A_n$ będą dowolnymi zbiorami. Wówczas

$\left|\bigcup_{i=1}^n A_i\right|=\sum_{i=1}^n\left|A_i\right| -\sum_{i,j\,:\,1 \le i < j \le n}\left|A_i\cap A_j\right| +$

$+ \sum_{i,j,k\,:\,1 \le i<j<k \le n}\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 \,$

[edytuj] Przykład

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

$+ \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.

[edytuj] 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 $\left|\bigcup_{i=1}^n A_i\right|$ jest on liczony jeden raz. W wyrażeniu $\sum_{i=1}^n\left|A_i\right| -\sum_{i,j\,:\,1 \le i < j \le n}\left|A_i\cap A_j\right| +\sum_{i,j,k\,:\,1 \le i<j<k \le n}\left|A_i\cap A_j\cap A_k\right|-\ \dots$

$\ \dots + (-1)^{n-1} \left|A_1\cap\cdots\cap A_n\right|$

ilość 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.