|
|
Linia 13: |
Linia 13: |
|
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|-</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> |
|
:<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. |
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.
Szablon:Stub