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

Q: Skąd biorą się naprzemienne znaki?

Z rachunku na wkładach: element należący do k zbiorów byłby policzony binomk1 razy, odjęty binomk2 razy, dodany binomk3 razy... Suma tych wkładów wynosi dokładnie 1, co pokazuje dwumian Newtona.

Q: Ile składników ma wzór dla n zbiorów?

2^n - 1 - tyle jest niepustych podzbiorów zbioru indeksów. Dla n = 3 daje to siedem składników, a dla n = 10 już ponad tysiąc; w praktyce zasadę stosuje się więc do niewielu zbiorów albo do zbiorów o regularnej strukturze.

Q: Czym różni się to od zasady szufladkowej?

Zasada szufladkowa dowodzi istnienia (gdzieś muszą być dwa przedmioty), a włączenia i wyłączenia liczą dokładnie. Obie należą do podstawowego warsztatu kombinatoryki.

Dla dwóch i trzech zbiorów:

$|A \cup B| = |A| + |B| - |A \cap B|,$

$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|.$

Ogólnie, dla $n$ zbiorów sumujemy przecięcia wszystkich rozmiarów z naprzemiennymi znakami:

$\left| \bigcup_{i=1}^{n} A_i \right| = \sum_{\emptyset \neq S \subseteq \{1,\ldots,n\}} (-1)^{|S|+1} \left| \bigcap_{i \in S} A_i \right|.$

Co mówi zasada

Chcemy policzyć, ile elementów należy do przynajmniej jednego ze zbiorów. Gdyby zbiory były rozłączne, wystarczyłoby dodać ich liczności. Gdy się przecinają, proste dodawanie liczy część elementów kilkakrotnie - trzeba więc odjąć nadmiar, ale przy odejmowaniu znów przesadzamy i część elementów wypada za dużo razy. Stąd naprzemienne znaki: dodajemy pojedyncze zbiory, odejmujemy pary, dodajemy trójki, odejmujemy czwórki i tak dalej.

Nazwa mówi dokładnie o tym: raz element włączamy, raz wyłączamy - aż saldo wyjdzie równo jeden.

Dowód

Pokaż dowódUkryj dowód

Pokażemy, że każdy element sumy jest po prawej stronie policzony dokładnie raz (a element spoza sumy - zero razy).

Krok 1. Wybieramy dowolny element. Niech $x$ należy do dokładnie $k \geq 1$ spośród zbiorów $A_1, \ldots, A_n$ .

Krok 2. Liczymy, w ilu składnikach się pojawia. Element $x$ należy do przecięcia $\bigcap_{i \in S} A_i$ dokładnie wtedy, gdy $S$ jest podzbiorem tych $k$ zbiorów, do których $x$ należy. Podzbiorów $j$ -elementowych jest $\binom{k}{j}$ , a każdy wchodzi ze znakiem $(-1)^{j+1}$ .

Krok 3. Sumujemy wkład elementu.

$\sum_{j=1}^{k} (-1)^{j+1} \binom{k}{j} = -\sum_{j=1}^{k} (-1)^{j} \binom{k}{j}.$

Krok 4. Korzystamy z dwumianu Newtona. Dla $k \geq 1$ :

$0 = (1 - 1)^k = \sum_{j=0}^{k} (-1)^j \binom{k}{j} = 1 + \sum_{j=1}^{k} (-1)^j \binom{k}{j},$

więc $\sum_{j=1}^{k} (-1)^j \binom{k}{j} = -1$ , a wkład elementu $x$ wynosi $-(-1) = 1$ .

Krok 5. Wniosek. Każdy element sumy jest policzony dokładnie raz, a element nienależący do żadnego zbioru nie pojawia się w żadnym składniku. Obie strony wzoru są więc równe. $\blacksquare$

Przykład 1 - podzielność

Ile liczb od $1$ do $100$ nie dzieli się przez $2$ , $3$ ani $5$ ?

Krok 1. Nazywamy zbiory. Niech $A$ - liczby podzielne przez $2$ , $B$ - przez $3$ , $C$ - przez $5$ .

$|A| = 50, \qquad |B| = 33, \qquad |C| = 20.$

Krok 2. Liczymy przecięcia (podzielność przez iloczyn):

$|A \cap B| = \left\lfloor \tfrac{100}{6} \right\rfloor = 16, \qquad |A \cap C| = \left\lfloor \tfrac{100}{10} \right\rfloor = 10, \qquad |B \cap C| = \left\lfloor \tfrac{100}{15} \right\rfloor = 6,$

$|A \cap B \cap C| = \left\lfloor \tfrac{100}{30} \right\rfloor = 3.$

Krok 3. Wstawiamy do wzoru.

$|A \cup B \cup C| = 50 + 33 + 20 - 16 - 10 - 6 + 3 = 74.$

Krok 4. Odpowiadamy na pytanie. Liczb podzielnych przez któryś z dzielników jest $74$ , więc pozostałych:

$100 - 74 = 26.$

Przykład 2 - problem szatniarki

W szatni $n$ osób oddało kapelusze. Roztargniony szatniarz rozdaje je losowo. Jakie jest prawdopodobieństwo, że nikt nie dostanie swojego?

Permutacje bez punktów stałych nazywamy nieporządkami. Niech $A_i$ - zbiór permutacji, w których $i$ -ta osoba dostała swój kapelusz. Chcemy policzyć permutacje spoza sumy zbiorów $A_i$ .

Krok 1. Liczności przecięć. Jeśli ustalimy $j$ osób, które dostały swoje kapelusze, resztę można rozdać dowolnie:

$\left| A_{i_1} \cap \ldots \cap A_{i_j} \right| = (n - j)!.$

Takich przecięć jest $\binom{n}{j}$ .

Krok 2. Zasada włączeń i wyłączeń.

$D_n = n! - \sum_{j=1}^{n} (-1)^{j+1} \binom{n}{j} (n-j)! = n! \sum_{j=0}^{n} \frac{(-1)^j}{j!}.$

Krok 3. Liczby dla małych $n$ .

$D_1 = 0, \quad D_2 = 1, \quad D_3 = 2, \quad D_4 = 9, \quad D_5 = 44.$

Krok 4. Zaskakująca granica. Prawdopodobieństwo, że nikt nie dostanie swojego kapelusza, to

$\frac{D_n}{n!} = \sum_{j=0}^{n} \frac{(-1)^j}{j!} \ \longrightarrow \ \frac{1}{e} \approx 0{,}3679.$

Wynik prawie nie zależy od liczby osób: przy pięciu osobach to $36{,}67\%$ , przy tysiącu - też około $36{,}79\%$ .

Przykład 3 - funkcja Eulera

Ile liczb od $1$ do $60$ jest względnie pierwszych z $60$ ?

Rozkład $60 = 2^2 \cdot 3 \cdot 5$ pokazuje, że przeszkadzają dzielniki $2$ , $3$ i $5$ . Stosując zasadę włączeń i wyłączeń do liczb podzielnych przez te dzielniki, dostajemy znany wzór:

$\varphi(n) = n \prod_{p \mid n} \left( 1 - \frac{1}{p} \right).$

Dla $n = 60$ :

$\varphi(60) = 60 \cdot \tfrac{1}{2} \cdot \tfrac{2}{3} \cdot \tfrac{4}{5} = 16.$

Funkcja $\varphi$ Eulera to jeden z filarów teorii liczb - pojawia się m.in. w uogólnieniu małego twierdzenia Fermata i w algorytmie RSA.

Po co to komu

Kombinatoryka - zliczanie obiektów spełniających „przynajmniej jeden z warunków” albo (przez dopełnienie) „żaden z warunków”.
Teoria liczb - sito Legendre’a i wzór na funkcję $\varphi$ ; wszystkie „sita” wywodzą się z tej zasady.
Prawdopodobieństwo - wzór na prawdopodobieństwo sumy zdarzeń, także tych zależnych.
Informatyka - zliczanie rozwiązań spełniających zestaw ograniczeń, algorytmy typu „inclusion-exclusion” w programowaniu dynamicznym nad podzbiorami.

Kto i kiedy

Wzór dla dwóch i trzech zbiorów znano od dawna; ogólną postać podał w 1718 roku Abraham de Moivre w The Doctrine of Chances, przy okazji rozważań o grach losowych. Nazwę „zasada włączeń i wyłączeń” spopularyzował w XIX wieku James Joseph Sylvester, a niezależnie wzór wyprowadził portugalski matematyk Daniel da Silva (1854).

Problem nieporządków - z kapeluszami, listami albo dopasowaniem kopert do adresów - postawił w 1708 roku Pierre Rémond de Montmort i to właśnie on jest najstarszym znanym zastosowaniem tej zasady.

Najczęstsze pytania

Skąd biorą się naprzemienne znaki? Z rachunku na wkładach: element należący do $k$ zbiorów byłby policzony $\binom{k}{1}$ razy, odjęty $\binom{k}{2}$ razy, dodany $\binom{k}{3}$ razy… Suma tych wkładów wynosi dokładnie $1$ , co pokazuje dwumian Newtona.

Ile składników ma wzór dla $n$ zbiorów? $2^n - 1$ - tyle jest niepustych podzbiorów zbioru indeksów. Dla $n = 3$ daje to siedem składników, a dla $n = 10$ już ponad tysiąc; w praktyce zasadę stosuje się więc do niewielu zbiorów albo do zbiorów o regularnej strukturze.

Czy zasada działa dla zbiorów nieskończonych? W tej postaci nie - mówi o licznościach zbiorów skończonych. Odpowiednikiem dla zdarzeń jest wzór na prawdopodobieństwo sumy, który wygląda identycznie i działa także dla zdarzeń o „nieskończonej” przestrzeni.

Jak liczyć elementy spoza sumy? Odejmując wynik od liczności całego zbioru - tak jak w przykładzie z liczbami do $100$ . To bardzo częsty schemat: łatwiej policzyć „przynajmniej jeden warunek” i odjąć, niż liczyć „żaden warunek” wprost.

Czym różni się to od zasady szufladkowej?Zasada szufladkowa dowodzi istnienia (gdzieś muszą być dwa przedmioty), a włączenia i wyłączenia liczą dokładnie. Obie należą do podstawowego warsztatu kombinatoryki.

Podsumowanie

Wzór: dodajemy pojedyncze zbiory, odejmujemy pary, dodajemy trójki - z naprzemiennymi znakami.
Dowód polega na sprawdzeniu, że wkład każdego elementu wynosi dokładnie $1$ ; kluczowa jest tożsamość $(1-1)^k = 0$ .
Klasyczne zastosowania: podzielność (sito), nieporządki (problem szatniarki) i wzór na funkcję $\varphi$ Eulera.
Prawdopodobieństwo, że nikt nie dostanie swojego kapelusza, dąży do $\tfrac{1}{e} \approx 36{,}8\%$ i praktycznie nie zależy od liczby osób.
Dla $n$ zbiorów wzór ma $2^n - 1$ składników - dlatego stosuje się go do małej liczby warunków.