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

Z Wikipedii

Masz nowe wiadomości (różnica z poprzednią wersją).

Niniejszy artykuł jest częścią cyklu kombinatoryka.

kombinacja bez powtórzeń
kombinacja z powtórzeniami

permutacja

wariacja bez powtórzeń
wariacja z powtórzeniami

liczby Stirlinga
liczby Bella
liczby Eulera

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

edytuj ten szablon

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

Zasada włączeń i wyłączeń - reguła kombinatoryczna, pozwalająca na zliczenie ilości elementów skończonej sumy mnogościowej skończonych zbiorów $A_1, A_2 \dots A_n$ :

$\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 \,$

Przykładowo, dla trzech zbiorów skończonych $A 1, A 2, A 3$ ilośc ich elementów ich sumy wyraża się wzorem:

$+ \left|A_1 \cap A_2 \cap A_3 \right|$

Formuła zapewnia to, że elementy znajdujące się jednocześnie w kilku spośród zbiorów $A_1, A_2 \dots A_n$ liczone są jeden raz.

Autorstwo zasady przypisywane jest zazwyczaj Abrahamowi de Moivre, chociaż bywa nazywana od nazwisk matematyków, Jamesa Josepha Sylvestera oraz Henriego Poincaré

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