Zasada włączeń i wyłączeń: Różnice pomiędzy wersjami
[wersja nieprzejrzana] | [wersja nieprzejrzana] |
m Anulowanie wersji nr 14082340 autora Sunridin - Bartku! Dwa minusy dadzą plus! |
m →Przykład: w jednej linii nie będzie wątpliwosci |
||
Linia 12: | Linia 12: | ||
===Przykład=== |
===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: |
Dla trzech zbiorów skończonych <math>A_1, A_2, A_3</math> liczba elementów ich sumy wyraża się wzorem: |
||
:<math>\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|-</math> |
:<math>\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| </math> |
||
:<math> + \left|A_1 \cap A_3 \right| -\left| A_2 \cap A_3 \right| + \left|A_1 \cap A_2 \cap A_3 \right| </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. |
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. |
Wersja z 13:18, 17 wrz 2008
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 będą dowolnymi zbiorami zaś . Wówczas
- ,
gdzie oznacza moc zbioru
Przykład
Dla trzech zbiorów skończonych liczba elementów ich sumy wyraża się wzorem:
Wzór zapewnia, że elementy znajdujące się jednocześnie w kilku spośród zbiorów liczone są dokładnie raz.
Dowód
Niech element należy dokładnie do spośród zbiorów . W sumie mnogościowej jest on liczony jeden raz. W wyrażeniu
ilość zliczeń pojedynczego elementu jest równa:
- ,
bowiem występuje on w zbiorach spośród , zbiorach spośród itd.
Na mocy rozwinięcia Newtona wyrażenie to jest równe , co dowodzi poprawności zasady włączeń i wyłączeń, bowiem element został policzony jeden raz.