thumb|Zasada włączeń 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 Niech będą dowolnymi skończonymi 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 ma on być liczony tylko jeden raz. W wyrażeniu
liczba 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 tylko jeden raz.
Uogólnienia Zasada włączeń i wyłączeń pozostaje prawdziwa, gdy nasze rozważania przeniesiemy na dowolną przestrzeń mierzalną Wtedy, twierdzenie przyjmuje postać:
Niech dana będzie przestrzeń mierzalna Dla dowolnych zbiorów mierzalnych (tj. należących do -algebry ) o skończonej mierze zachodzi
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ń wzór ten przyjmuje postać
i ogólnie
gdzie jest prawdopodobieństwem, określonym w danym eksperymencie losowym (przestrzeni probabilistycznej).
Bibliografia
Linki zewnętrzne
Oskar Skibski, Zasada Włączeń i Wyłączeń [w:] Matematyka Dyskretna, kanał autorski na YouTube, 26 marca 2020 [dostęp 2026-01-17] – nagranie w ramach kursu, Wydział Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego (MIM UW). [dostęp 2024-03-07]. Inclusion-and-exclusion principle , Encyclopedia of Mathematics, encyclopediaofmath.org [dostęp 2026-01-17].
Kategoria:Twierdzenia teorii miary Kategoria:Twierdzenia probabilistyki Kategoria:Twierdzenia kombinatoryki