Zasada włączenia i wykluczenia w kombinatoryce: łatwe obliczanie rozmiaru zestawu

Zasada włączenia-wyłączenia to technika stosowana w kombinatoryce do obliczania rozmiaru zbioru poprzez podzielenie go na mniejsze podzbiory i zliczenie ich przecięcia. Opiera się na założeniu, że jeśli mamy dwa zbiory, A i B, i chcemy policzyć elementy znajdujące się w obu zbiorach, możemy to zrobić poprzez odejmowanie elementów znajdujących się tylko w A od całkowitej liczby elementów w A, a następnie dodając elementy, które są tylko w B.

Bardziej formalnie, niech A i B będą dwoma zbiorami i niech |A| będzie liczbą elementów w A. Zatem zasada włączenia-wykluczenia stwierdza, że:

|A ∪ B| = |A| + |B| - |A ∩ B|

gdzie |A ∪ B| jest liczbą elementów w związku A i B oraz |A ∩ B| to liczba elementów znajdujących się zarówno w A, jak i B.

Idea tego wzoru jest taka, że możemy obliczyć rozmiar sumy dwóch zbiorów, najpierw licząc liczbę elementów w każdym zestawie z osobna, a następnie odejmując elementy, które znajdują się tylko w jednym ze zbiorów (tj. są elementami przecięcia). To daje nam całkowitą liczbę elementów w związku, która jest sumą liczby elementów w każdym zestawie minus liczba elementów znajdujących się tylko w jednym ze zbiorów.…
Załóżmy na przykład, że mamy dwa zbiory: A = {1, 2, 3} i B = {4, 5, 6}. Aby obliczyć wielkość ich związku, korzystając z zasady włączeń i wykluczeń, najpierw liczymy liczbę elementów w każdym zbiorze osobno:

|A| = 3
|B| = 3

Następnie obliczamy liczbę elementów znajdujących się w obu zbiorach, licząc ich przecięcie:

|A ∩ B| = 2 (ponieważ 1 i 2 są w obu zbiorach)

Teraz możemy skorzystać z zasady włączeń-wykluczeń, aby obliczyć wielkość związku:

|A ∪ B| = |A| + |B| - |A ∩ B|
= 3 + 3 - 2
= 6

Więc rozmiar sumy A i B wynosi 6.

Zasada włączenia-wykluczenia ma wiele zastosowań w kombinatoryce, takich jak liczenie liczby permutacji, kombinacji i rozwiązań do równań. Jest to potężne narzędzie do rozwiązywania problemów z liczeniem, które można wykorzystać do uproszczenia skomplikowanych obliczeń.