Αρχή Εγκλεισμού-Αποκλεισμού

Εισαγωγή στην Αρχή Εγκλεισμού-Αποκλεισμού

Η αρχή εγκλεισμού-αποκλεισμού (ή αρχή συμπερίληψης-αποκλεισμού) είναι ένα ισχυρό εργαλείο της συνδυαστικής για τον υπολογισμό του πλήθους στοιχείων σε ενώσεις συνόλων. Μας επιτρέπει να αποφύγουμε τη διπλή καταμέτρηση στοιχείων που ανήκουν σε περισσότερα από ένα σύνολα.

Η Αρχή για Δύο Σύνολα

Για δύο σύνολα $A$ και $B$:

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

Ερμηνεία: Αθροίζοντας $|A|$ και $|B|$, τα στοιχεία της τομής $A \cap B$ μετρώνται δύο φορές. Αφαιρούμε μία φορά το $|A \cap B|$ για να διορθώσουμε.

Διάγραμμα Venn

Η αρχή απεικονίζεται εύκολα με διαγράμματα Venn, όπου φαίνεται ότι η τομή «επικαλύπτεται» στο άθροισμα.

Η Αρχή για Τρία Σύνολα

Για τρία σύνολα $A$, $B$, $C$:

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

Ερμηνεία:

1. Αθροίζουμε τα τρία σύνολα (κάποια στοιχεία μετρώνται πολλαπλές φορές)
2. Αφαιρούμε τις δυαδικές τομές (διορθώνουμε τη διπλή καταμέτρηση)
3. Προσθέτουμε την τριαδική τομή (αυτά τα στοιχεία αφαιρέθηκαν υπερβολικά)

Γενική Μορφή

Για $n$ σύνολα $A_1, A_2, ..., A_n$:

$$\left|\bigcup_{i=1}^{n} A_i\right| = \sum_{i} |A_i| - \sum_{i<j} |A_i \cap A_j| + \sum_{i<j<k} |A_i \cap A_j \cap A_k| - ... + (-1)^{n+1} |A_1 \cap A_2 \cap ... \cap A_n|$$

ή συμβολικά:

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

Εφαρμογή: Πλήθος Συμπληρώματος

Αν $S$ είναι το σύμπαν και $A_1, ..., A_n$ υποσύνολα του $S$, το πλήθος στοιχείων που δεν ανήκουν σε κανένα $A_i$ είναι:

$$|S| - |A_1 \cup A_2 \cup ... \cup A_n|$$

Κλασική Εφαρμογή: Η Συνάρτηση Euler

Η συνάρτηση $\phi(n)$ του Euler μετρά πόσοι ακέραιοι από 1 έως $n$ είναι πρώτοι μεταξύ τους με το $n$.

Αν $n = p_1^{a_1} \cdot p_2^{a_2} \cdot ... \cdot p_k^{a_k}$, τότε:

$$\phi(n) = n \left(1 - \frac{1}{p_1}\right)\left(1 - \frac{1}{p_2}\right)...\left(1 - \frac{1}{p_k}\right)$$

Εφαρμογή: Πρόβλημα Αναστατώσεων

Μια αναστάτωση (derangement) είναι μια μετάθεση όπου κανένα στοιχείο δεν βρίσκεται στην αρχική του θέση.

Ο αριθμός αναστατώσεων $n$ στοιχείων είναι:

$$D_n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!} \approx \frac{n!}{e}$$

Παράδειγμα: Για $n=4$: $D_4 = 24 \cdot (1 - 1 + \frac{1}{2} - \frac{1}{6} + \frac{1}{24}) = 24 \cdot \frac{9}{24} = 9$

Εφαρμογή: Surjective Functions

Ο αριθμός επί συναρτήσεων από σύνολο $n$ στοιχείων σε σύνολο $k$ στοιχείων:

$$k! \cdot S(n,k)$$

όπου $S(n,k)$ είναι ο αριθμός Stirling δεύτερου είδους.