Zasada włączeń i wyłączeń: Różnice pomiędzy wersjami

Z Wikipedii, wolnej encyklopedii
[wersja nieprzejrzana][wersja nieprzejrzana]
Usunięta treść Dodana treść
DragonBot (dyskusja | edycje)
MastiBot (dyskusja | edycje)
Linia 37: Linia 37:
[[de:Prinzip von Inklusion und Exklusion]]
[[de:Prinzip von Inklusion und Exklusion]]
[[en:Inclusion-exclusion principle]]
[[en:Inclusion-exclusion principle]]
[[es:Principio de inclusión-exclusión]]
[[eo:Inkluziveco-ekskluda principo]]
[[eo:Inkluziveco-ekskluda principo]]
[[fr:Principe d'inclusion-exclusion]]
[[fr:Principe d'inclusion-exclusion]]

Wersja z 12:06, 25 gru 2008

Zasada właczeń 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 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