Włączenie-i-wykluczenie: Liczenie Złomów Bez Podwójnego Liczenia

Problem z prostym dodawaniem rozmiarów zbiorów

Chcemy policzyć ile osób w pokoju mówi francuski lub niemiecki. Dodanie liczby mówców francuskiego do liczby mówców niemieckiego nadliczbuje tych, którzy mówią oba języki — są liczeni dwa razy. Rozwiązanie jest jasne, jak tylko to zobaczyć: odejmij przecięcie z powrotem. |A ∪ B| = |A| + |B| − |A ∩ B|. Ta jedna korekcja jest siedzącem dla zasady włączenia-i-wykluczenia, a interesujące jest to, co się dzieje, gdy skalujemy to z dwóch do trzech, dziesięciu lub sto osiemdziesięciu zbiorów.

Trzy zbiory: dodawanie, odejmowanie, dodawanie ponownie

W przypadku trzech nadmiarowo przecinających się zbiorów, diagram Venn ma siedem różnych regionów. Dodając |A| + |B| + |C|, przeliczamy każdą dwuczłonową przeciętność dwa razy i potem pomniejszamy trójczłonowe przecięcie po odejmowaniu parowych przecięć — region, w którym wszystkie trzy zbiory przecinają się, jest dodawany trzykrotnie, odejmowany trzykrotnie i musi zostać dodany ponownie, aby uzyskać poprawną liczbę:

|A ∪ B ∪ C| = |A| + |B| + |C| − |A∩B| − |A∩C| − |B∩C| + |A∩B∩C| wzór: alternatywny dodawanie i odejmowanie, jedna czynność dla każdego możliwego rozmiaru przecięcia Ogólna reguła dla n zbiorów zachowuje się w taki sposób, że alternatywnie dodaje i odejmuje na podstawie liczby zbiorów w każdym przecięciu: dodaje wszystkie jednozbierniki, odejmuje wszystkie dwuczłonowe przecięcia, dodaje wszystkie trójczłonowe przecięcia, odejmuje wszystkie czwoczłonowe przecięcia i tak dalej, kończąc na jednej czynności dla przecięcia wszystkich n zbiorów, oznaczonej znakiem (−1)^(n+1).

|A ∪ B ∪ C| = |A| + |B| + |C|
              − |A∩B| − |A∩C| − |B∩C|
              + |A∩B∩C|

pattern: alternate + and −, one term per possible intersection size

Dlaczego alternujący sumator działa: liczenie każdego elementu dokładnie raz

Jednoznaczny sposób na pokazanie, dlaczego ten wzór zawsze daje prawidłową odpowiedź polega na sprawdzeniu, ile razy dany element jest liczone. Wybierz element, który należy do dokładnie k z n zbiorów. Ten element przyczynia się do C(k,1) wyrazów jednoelementowych, C(k,2) wyrazów dwuelementowych i tak dalej aż do C(k,k). Alternujący sumator tych współczynników dwumianowych, C(k,1) − C(k,2) + C(k,3) − ..., zawsze równa się dokładnie 1 dla dowolnego k ≥ 1 ( bezpośredni konsekwencja twierdzenia dwumianowego stosowanego do (1−1)^k = 0). Stąd każdy element, który należy do przynajmniej jednego zbioru, jest liczone dokładnie raz w końcowej sumie, niezależnie od tego, ile zbiórów przypadkiem zawiera — to całe dowodzenie, a to jest powód, dla którego wzór generalizuje się prosto do dowolnej liczby zbiorów.

Derangementy: klasyczne zastosowanie zasady włączenia-i-wykluczenia

Klasycznym zastosowaniem zasady włączenia-i-wykluczenia jest liczenie derangmentów — mnożeń n przedmiotów, w których żaden przedmiot nie znajduje się na swoim oryginalnym miejscu (problem „sprzątania kapeluszy”: n osób sprawdza n kapeluszy, w ilu sposobach każda z nich może otrzymać kapelusz inną osobę?). Niech A_i będzie zbiorem mnożeń, w których przedmiot i znajduje się na swoim oryginalnym miejscu; chcesz wszystko poza unią wszystkich A_i. Zasada włączenia-i-wykluczenia dla tych n zbiorów daje:

D(n) = n! · Σ_{k=0}^{n} (−1)^k / k! D(1) = 0 D(2) = 1 D(3) = 2 D(4) = 9 D(5) = 44 przy rosnącym n, D(n)/n! → 1/e ≈ 0.3679 Ostatnia linia jest małą matematyczną magią: ułamek wszystkich mnożeń, które są pełnymi derangmentami, zbiega do 1/e, co oznacza, że około 37% losowych permutacji pozostawiają wszystkie przedmioty na innych miejscach, prawie niezależnie od tego, jak duży jest n, gdy n przekroczy kilka.

D(n) = n! · Σ_{k=0}^{n} (−1)^k / k!

D(1) = 0
D(2) = 1
D(3) = 2
D(4) = 9
D(5) = 44

as n grows, D(n)/n! → 1/e ≈ 0.3679

Taka technika liczy surjekcje i sito Eratostenesa

Zasada włączenia-i-wykluczenia jest jednym z najczęściej używanych narzędzi w kombinatoryce, ponieważ wielu problemów liczących redukuje się do 'liczenia rzeczy, które unikają listy określonych złych właściwości'. Liczenie surjekcji (funkcji od n-elementowego zbioru na m-elementowy zbiór, osiągającego każdą docelową wartość) jest zasadą włączenia-i-wykluczenia dla 'docelowa j jest pominięta'. Sieć arytmetyczna Eratostenesa do liczenia liczb mniejszych lub równych N bez żadnego z wybranych czynników pierwszych to zasada włączenia-i-wykluczenia dla 'podzielnych przez czynnik pierwszy p_i'. Gdzie bezpośrednie liczenie prowadzi do nadliczania przypadków złych, które się nakładają, wzór dodawanie-odejmowanie-dodawanie jest obwieszczeniem zwykle najprostszym i najskuteczniejszym sposobem na poprawienie tego dokładnie.

Często zadawane pytania