Metoda włączeń i wyłączeń cz I.

Zdarza się, że prosto jest policzyć liczbę elementów przecięcia kilku zbiorów, natomiast trudno liczbę elementów sumy tychże zbiorów. Przedstawimy metodę, dzięki której problem wyznaczenia sumy zbiorów sprowadzimy do wyznaczenia ich przecięć.

Dla dwóch zbiorów sytuacja wygląda prosto. Dodajemy ilość elementów zbioru pierwszego do ilości elementów zbioru drugiego i odejmujemy ilość elementów przecięcia obu zbiorów.
Dla trzech zbiorów sprawa się nieco komplikuje, ale wciąż wzór wygląda przystępnie. Najpierw sumujemy liczbę elementów poszczególnych zbiorów. Następnie odejmujemy liczbę elementów w przecięciach każdych dwóch zbiorów. Na końcu dodajemy liczbę elementów znajdujących się we wszystkich zbiorach.
Dla czterech zbiorów wzór robi się już nieczytelny. Bardzo niemiły jest też wzór dla dowolnego n:
Gdzie P₊(n) oznacza zbiór potęgowy zbioru {1, 2, ..., n} bez zbioru pustego.

Nie przejmuj się jeśli tego wzoru nie rozumiesz. Przedstawię teraz o wiele prostszą definicję metody włączeń i wyłączeń, którą łatwiej zapamiętać i łatwiej zastosować.

Aby znaleźć liczbę elementów sumy zbiorów A₁, A₂, ..., A_n znajdź liczby elementów wszystkich możliwych przecięć zbiorów spośród {A₁, A₂, ..., A_n}, dodaj do siebie wyniki uzyskane dla przecięć nieparzystej liczby zbiorów, a następnie odejmij wyniki uzyskane dla przecięć parzystej liczby zbiorów.

Dowód poprawności tej metody znajduje się na Wikipedii (http://pl.wikipedia.org/wiki/Zasada_w%C5%82%C4%85cze%C5%84_i_wy%C5%82%C4%85cze%C5%84).

Wadą tej metody jest oczywiście złożoność. Gdy mamy N zbiorów policzymy tą metodą liczebność 2^N-1 zbiorów. Niestety, niekiedy jest to najszybszy sposób.

W części drugiej przedstawię kilka przykładów zadań, które wymagają użycia tej metody.