zasada włączeń i wyłączeń

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

Zdarza się w zadaniach kombinatorycznych (i nie tylko), że chcemy policzyć liczbę elementów zbioru, który jest sumą innych (niekoniecznie rozłącznych) zbiorów. W takiej sytuacji przydaje się zasada włączeń i wyłączeń.

Rozważmy na początek następujące zadanie:

Ile jest liczb całkowitych dodatnich nie większych niż 10000 podzielnych co najmniej przez jedną z liczb: 2 lub 3?

Oznaczmy przez \(X_i\) zbiór liczb całkowitych dodatnich, nie większych niż 1000 oraz podzielnych przez \(i\), a przez \(|X_i|\) liczbę jego elementów.

Rozwiązaniem zadania jest oczywiście liczba \(|X_2\cup X_3|\). Nie możemy jednak ot tak sobie dodać \(|X_2|+|X_3|\) ponieważ zbiory \(X_2\) oraz \(X_3\) nie są rozłączne. Innymi słowy są liczby podzielne zarówno przez 2 oraz przez 3, tj. podzielne przez 6. Od sumy \(|X_2|+|X_3|\) musimy odjąć jeszcze \(|X_2\cap X_3|=|X_6|\). Dokładniej, \[|X_2|=5000,\ |X_3|=3333,\ |X_6|=1666\] czyli \(|X_2\cup X_3|=6667\).

Powyższą sytuację możemy przedstawić na rysunku.
reguła włączeń i wyłączeń

Widać na nim dobitnie, że dla dwu zbiorów \(A\) oraz \(B\) liczba elementów ich sumy jest równa \[|A\cup B|=|A|+|B|-|A\cap B|.\]

Analogiczną sytuację możemy spotkać w prawdopodobieństwie. Wzór na prawdopodobieństwo sumy zdarzeń wszak wygląda tak: \[P(A\cup B)=P(A)+P(B)-P(A\cap B)\] Nie ma w tym przypadku, gdyż zdarzenia są de facto zbiorami. Podobnie, prawdopodobieństwo możemy zastąpić miarą. Zarówno liczba elementów zbioru skończonego jak i prawdopodobieństwo, to szczególne przypadki miar.

Ci co spotkali się z pojęciem Charakterystyki Eulera wiedzą być może, że w pewnych przypadkach zachodzi analogiczna równość. Innymi słowy, zasada włączeń i wyłączeń pojawia się w matematyce w wielu miejscach. Nie tylko w kombinatoryce.

Pierwsze zadanie było proste, bo były tylko dwa zbiory. A co, gdy jest ich więcej? Może uda się dostrzec jakąś regułę pozwalającą w miarę łatwo policzyć liczbę elementów sumy zbiorów \[A_1\cup A_2\cup A_3\cup\ldots\cup A_n?\] Dodajmy w naszym zadaniu jeszcze jedną liczbę.

Ile jest liczb całkowitych dodatnich nie większych niż 10000 podzielnych co najmniej przez jedną z liczb: 2, 3 lub 5?

Tutaj od liczby \(|X_2|+|X_3|+|X_5|\) musimy odjąć:

  • ilość liczb podzielnych jednocześnie przez 2 oraz 3 (tj. \(|X_2\cap X_3|\)),
  • ilość liczb podzielnych jednocześnie przez 2 oraz 5 (tj. \(|X_2\cap X_5|\)),
  • ilość liczb podzielnych jednocześnie przez 3 oraz 5 (tj. \(|X_3\cap X_5|\)).

Czy to już koniec? Oczywiście, że nie! Bo co trzeba zrobić z liczbami podzielnymi jednocześnie przez 2, 3 oraz 5? Spójrzmy na poniższy rysunek. Zobrazowano na nim zbiory \(X_2, X_3, X_5\) (oznaczone stosownymi liczbami).

zasada włączeń i wyłączeń

Dodając \(|X_2|+|X_3|+|X_5|\) dwukrotnie, nazwijmy to, włączamy elementy zbiorów \(X_2\cap X_3, X_2\cap X_5\) oraz \(X_3\cap X_5\), bo np. zbiór \(X_2\cap X_3\) jest zawarty zarówno w \(X_2\) jak i w \(X_3\) itd.

Musimy więc odjąć sumę \(|X_2\cap X_3|+|X_2\cap X_5|+|X_3\cap X_5|\). W tym momencie, to co należy do tylko jednego zbioru (zaznaczone kolorami innymi niż biały) zostało włączone raz.

reguła włączeń i wyłączeń

Podobnie to co należy do dokładnie dwu zbiorów zostało włączone dokładnie raz.

włączenia i wyłączenia

Pozostaje część wspólna wszystkich trzech zbiorów. Została ona najpierw włączona trzykrotnie, gdy dodawaliśmy \(|X_2|+|X_3|+|X_5|\). Następnie została trzykrotnie, nazwijmy to, wyłączona, gdy odjęliśmy \(|X_2\cap X_3|+|X_2\cap X_5|+|X_3\cap X_5|\). Czyli aby otrzymać ostateczną odpowiedź musimy jeszcze dodać \(|X_2\cap X_3\cap X_5|\).

Dostaliśmy następującą zależność dla trzech dowolnych zbiorów \(A, B\) oraz \(C\): \[|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|.\]

Ponieważ \[|X_5|=2000,\ |X_2\cap X_5|=|X_{10}|=1000,\ |X_3\cap X_5|=|X_{15}|=666\] oraz \[|X_2\cap X_3\cap X_5|=|X_{30}|=333,\]
to \[|X_2\cup X_3\cup X_5|=7334\]

Otrzymana zależność nie jest już taka prosta jak wcześniej. Nie jest też przesadnie skomplikowana. Sugeruje ona dwie rzeczy. Po pierwsze, że przy większej liczbie zbiorów otrzymamy jeszcze bardziej skomplikowane zależności. A po drugie, że znalezienie ogólnej zależności wydaje się w zasięgu.

Rozważmy teraz sytuację ogólną. Mamy \(n\) zbiorów skończonych \[A_1, A_2,\ldots, A_n,\] które niekoniecznie muszą być rozłączne. Jak obliczyć liczbę elementów ich sumy\[A_1\cup A_2\cup\ldots\cup A_n?\] Znowu zaczniemy od zsumowania \[|A_1|+|A_2|+\cdots+|A_n|.\] Elementy należące do dokładnie jednego zbioru zostały włączone dokładnie raz. Natomiast należące do więcej niż jednego zbioru, wielokrotnie. Te należące do dokładnie dwu zbiorów, uwzględniliśmy na tym etapie dwukrotnie. Musimy więc je teraz wyłączyć. Robimy to jak wcześniej, tzn. odejmujemy liczby \(|A_i\cap A_j|\) dla wszystkich możliwych par \(i\neq j\).

Krok ten spowodował, że mamy teraz jednokrotnie uwzględnione elementy należące do dokładnie jednego lub dokładnie dwu zbiorów. Do tego wyłączyliśmy pewną ilość razy elementy należące do dokładnie trzech lub więcej zbiorów.

Ogólna zależność, tj. zasada włączeń i wyłączeń wygląda następująco:
\[|A_1\cup A_2\cup\ldots\cup A_n|=\sum_{1\leqslant i\leqslant n}|A_i|-\sum_{1\leqslant i\lt j\leqslant n}|A_i\cap A_j|+\ldots +(-1)^{n-1}|A_1\cap A_2\cap\ldots\cap A_n|\]

Najpierw włączamy wszystkie zbiory \(A_i\), potem wyłączamy wszystkie \(A_{i_1}\cap A_{i_2}\), włączamy wszystkie \(A_{i_1}\cap A_{i_2}\cap A_{i_3}\), wyłączamy wszystkie \(A_{i_1}\cap A_{i_2}\cap A_{i_3}\cap A_{i_4}\) i tak dalej.

Teraz przekonamy się, że powyższy wzór istotnie jest prawdziwy. Niech \(x\in A_1\cup A_2\cup\ldots\cup A_n\) należy do dokładnie \(k\) zbiorów. Wówczas dodając \(|A_1|+|A_2|+\cdots+|A_n|\) włączamy do \(k\) razy. Odejmując wszystkie liczby \(|A_i\cap A_j|\) wyłączamy go tyle razy, ile jest par zbiorów \(A_i, A_j\) do których należy \(x\). Takich par jest naturalnie \({k\choose 2}\). Ogólnie, jeżeli \(m\leqslant k\), to dodając wszystkie możliwe liczby \[|A_{i_1}\cap A_{i_2}\cap\ldots\cap A_{i_m}|\] element \(x\) zostaje włączony \({k\choose m}\) razy. Gdy zaś \(m\gt k\), to z założenia \(x\) nie jest elementem części wspólnej \(m\) zbiorów. Ostatecznie \(x\) został włączony \[\sum_{m=1}^k(-1)^m{k\choose m}={k\choose 1}-{k\choose 2}+{k\choose 3}-\cdots+(-1)^k{k\choose k}\] razy. A ponieważ \[\sum_{m=0}^k(-1)^m{k\choose m}=\sum_{m=0}^k(-1)^m\cdot 1^{k-m}\cdot{k\choose m}=(1-1)^k=0,\] to
\[\sum_{m=1}^k(-1)^m{k\choose m}=1\] i zasada włączeń i wyłączeń została udowodniona.
\(\)

Uwidacznia się jednak pewna wada używania tej zasady do rozwiązywania zadań. Gdy zbiorów jest więcej niż 3, to liczba obliczeń jakie musimy wykonać jest już całkiem spora. A i nawet w przypadku trzech zbiorów, jak mogliśmy zobaczyć w ostatnim zadaniu, wykonanie wszystkich obliczeń może być nieco uciążliwe. Czasami jednak sytuacja nie jest taka zła.

Jeżeli wszystkie zbiory \(A_{i}\) mają tę samą liczbę elementów, podobnie wszystkie \(A_{i_1}\cap A_{i_2}\) itd., to liczba elementów zbioru \(A_1\cup A_2\cup\ldots\cup A_n\) jest równa \[{n\choose 1}|A_1|-{n\choose 2}|A_1\cap A_2|+\cdots+(-1)^{m-1}{n\choose m}|A_1\cap A_2\cap\ldots\cap A_m|+\cdots \]
tj. \[|A_1\cup A_2\cup\ldots\cup A_n|=\sum_{i=1}^n{n\choose i}(-1)^{i-1}|A_1\cap A_2\cap\ldots\cap A_i|\]

Spójrzmy teraz na następujące zadanie:

Na ile sposobów z talii 52 kart można wybrać 5 kart tak, aby otrzymać co najmniej jednego asa, co najmniej jednego króla i co najmniej jedną damę?

Gwoli ścisłości, mówiąc sposób mamy na myśli 5 kart jako zbiór. Nie interesuje nas żadna ich kolejność.

Jedna z pierwszych odpowiedzi jaka przychodzi do głowy wielu osobom, to \[4^3\cdot {49 \choose 2}=75264.\] Bo jednego asa, króla oraz damę możemy na \(4^3\) sposobów (w standardowej talii kart są 4 asy, 4 króle i 4 damy). Do tego zostają dwie pozostałe karty, które możemy już wybrać dowolnie.

Nie jest to jednak prawidłowa odpowiedź. Pomysł takiego ,,rozwiązania” polega na sztucznym rozbiciu zestawu 5 kart na dwie części – nazwijmy je A oraz B. W części A znajduje się to co musi się znajdować, czyli as, król oraz dama. W części B mamy zaś pozostałe dwie karty. Takie sztuczne rozbicie zbioru kart na dwie części nie uwzględnia jednej rzeczy. Spójrzmy na przykładowe dwa wyniki takiego losowania: \[A♡ K♡ D♡ – A♤ D♤\] oraz \[A♤ K♡ D♡ – A♡ D♤\]

W obu przypadkach mamy dokładnie takie same zestawy kart. Różnica jest jedynie w położeniu asów. Za pierwszym razem as A♡ pojawił się w części A, zaś as A♤ w B. W przypadku drugim, asy zamieniły się miejscami. Zestawy kart są jednak takie same. Tego właśnie nie bierze pod uwagę taka próba rozwiązania. W wylosowanych pięciu kartach mogą znajdować dwa lub nawet trzy asy, króle czy damy.

Znając zasadę włączeń i wyłączeń bez trudu powinniśmy dostrzec, że rozwiązaniem zadania jest \[|A\cup K\cup D|,\] gdzie \(A\), to zbiór tych sposobów na jakie można wybrać 5 kart, aby był co najmniej jeden as. Podobnie \(K\), to sposoby z królem, a \(D\) z damą. Co więcej, zbiory te mają dokładnie po tyle samo elementów, bo w talii mamy po 4 asy, króle oraz damy. Również zbiory \(A\cap K, A\cap D\) oraz \(K\cap D\) mają te same liczby elementów. Tylko czy obliczenie \(|A|, |A\cap K|\) oraz \(|A\cap K\cap D|\) jest aby na pewno takie łatwe?

Znacznie łatwiej jest policzyć ilość wyborów 5 kart z talii nie zawierających asa niż zawierających. Podobnie w przypadku wyborów nie zawierających ani asa ani króla oraz tych nie zawierających ani asa ani króla ani damy.

Pięć kart, wśród których nie ma ani jednego asa jesteśmy w stanie wybrać na \({48\choose 5}\) sposobów. Tak aby nie było żadnego asa oraz żadnego króla na \({44\choose 5}\), a aby nie było ani asa ani króla ani damy na \({40\choose 5}\) sposobów. Wobec tego, zasada włączeń i wyłączeń mówi nam, że sposobów wylosowania pięciu kart nie spełniających warunków zadania jest \[3\cdot{48\choose 4}-3\cdot {44\choose 4}+{40\choose 4}.\] Zatem ostateczna odpowiedź, to \[{52\choose 5}-3\cdot{48\choose 4}+3\cdot {44\choose 4}-{40\choose 4}=62 064.\]

Ciekawym zastosowaniem zasady włączeń i wyłączeń jest problem liczenia tzw. nieporządków, tj. permutacji nie mających punktów stałych czyli takich punktów, że \(\pi(i)=i\). Mówiąc mniej matematycznie, jeżeli wyciągamy po kolei wszystkie karty z talli starając się zgadnąć każdą po kolei, to sytuacja, gdy ani razu nie zgadniemy karty jest przykładem nieporządku.

Niech \(\mathcal P_i\) oznacza zbiór permutacji \(\pi\) zbioru \(\{1,2,\ldots,n\}\) takich, że \(\pi(i)=i\). Wówczas liczba nieporządków jest równa \[n!-\left|\bigcup_{i=1}^n\mathcal P_i\right|.\] Aż korci aby skorzystać tutaj z zasady włączeń i wyłączeń. Tym bardziej, że jak nietrudno się przekonać, prawdziwa jest równość \[|\mathcal P_{i_1}\cap\mathcal P_{i_2}\cap\ldots\cap\mathcal P_{i_k}|=(n-k)!\] Bo gdy \(\pi(i_1)=i_1,\pi(i_2)=i_2,\ldots,\pi(i_k)=i_k\) oraz \(j\notin \{i_1,i_2,\ldots,i_k\}\), to \(\pi(j)\) może mieć dowolną wartość różną od \(i_1,i_2,\ldots,i_k\). Innymi słowy, zbiór \(\mathcal P_{i_1}\cap\mathcal P_{i_2}\cap\ldots\cap\mathcal P_{i_k}\) ma taką samą liczbę elementów co zbiór permutacji zbioru \((n-k)\)-elementowego.

Wobec tego \[\left|\bigcup_{i=1}^n\mathcal P_i\right|=\sum_{i=1}^n (-1)^{i+1}{n\choose i}(n-i)!=n!\sum_{i=1}^n\dfrac{(-1)^{i+1}}{i!}\] a zatem liczba nieporządków \(D(n)\) zbioru \(n\)-elementowego jest równa
\[\begin{array}{lll}D(n)=n!-n!\sum\limits_{i=1}^n\frac{(-1)^{i+1}}{i!} & = & n! – n! +n!(\frac{1}{2!}-\frac{1}{3!}+\cdots +\frac{(-1)^n}{n!})\\ & = & n!\sum\limits_{i=0}^n\frac{(-1)^{i}}{i!}\end{array}
\]

Wzór na liczbę nieporządków możemy zapisać w bardziej eleganckiej, a zarazem nieco zaskakującej, formie. \[D(n)=\left[\dfrac{n!}{e}\right],\] gdzie \(e\), to słynna matematyczna stała będąca m.in. podstawą logarytmu naturalnego. Zaś \([x]\) oznacza liczbę całkowitą najbliższą liczbie \(x\). Ponieważ liczba \(e\) jest niewymierna, to \(n!\cdot e^{-1}\) na pewno nie jest sumą liczby całkowitej i \(0,5\). Wobec czego powyższy wzór jednoznacznie określa pewną liczbę całkowitą.

Wzór ten wynika z tego, że \[e^{-1}=\sum_{n=0}^{\infty}\frac{(-1)^n}{n!}\] oraz \[\left[n!e^{-1}-D(n)\right]=n!\left|\sum_{i=n+1}^\infty\frac{(-1)^i}{i!}\right|\lt \frac{n!}{(n+1)!}=\frac{1}{n+1}\leqslant\frac{1}{2}\]

Odpowiedz

Twój adres e-mail nie zostanie opublikowany. Wymagane pola są oznaczone *