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

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

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

TwierdzenieEdytuj

Niech   będą dowolnymi skończonymi zbiorami zaś   Wówczas

 

gdzie   oznacza moc zbioru  

PrzykładEdytuj

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ódEdytuj

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ólnieniaEdytuj

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

BibliografiaEdytuj

  • Jacek Jakubowski, Rafał Sztencel: Wstęp do teorii prawdopodobieństwa. Warszawa: SCRIPT, 2001, s. 11–12.
  • Zbigniew Bobiński, Lev Kourliandtchik, Mirosław Uscki: Miniatury matematyczne. Elementarne metody w kombinatoryce. Toruń: Wydawnictwo Aksjomat, 2002, s. 11–15. ISBN 83-87329-35-5.