Αρχές Απαρίθμησης

Εισαγωγή στις Αρχές Απαρίθμησης

Οι αρχές απαρίθμησης αποτελούν τη βάση της συνδυαστικής και μας επιτρέπουν να μετράμε το πλήθος των δυνατών τρόπων για την πραγματοποίηση μιας εργασίας ή τη δημιουργία μιας δομής. Είναι θεμελιώδεις για τον υπολογισμό πιθανοτήτων και την επίλυση προβλημάτων καταμέτρησης.

Αρχή Αθροίσματος (Διάζευξη)

Η αρχή του αθροίσματος χρησιμοποιείται όταν έχουμε αμοιβαία αποκλειόμενες επιλογές.

Διατύπωση: Αν μια εργασία $A$ μπορεί να γίνει με $m$ τρόπους Ή μια εργασία $B$ μπορεί να γίνει με $n$ τρόπους, και οι εργασίες $A$, $B$ δεν μπορούν να συμβούν ταυτόχρονα, τότε η εργασία «$A$ ή $B$» μπορεί να γίνει με:

$$m + n \text{ τρόπους}$$

Γενίκευση: Για $k$ αμοιβαία αποκλειόμενες εργασίες με $n_1, n_2, ..., n_k$ τρόπους αντίστοιχα:

$$n_1 + n_2 + ... + n_k = \sum_{i=1}^{k} n_i \text{ τρόπους}$$

Παράδειγμα Εφαρμογής

Αν σε μια βιβλιοθήκη υπάρχουν 12 βιβλία μαθηματικών, 8 βιβλία φυσικής και 5 βιβλία χημείας, με πόσους τρόπους μπορούμε να διαλέξουμε ένα βιβλίο;

$$12 + 8 + 5 = 25 \text{ τρόποι}$$

Αρχή Γινομένου (Σύζευξη)

Η αρχή του γινομένου χρησιμοποιείται όταν έχουμε διαδοχικές ανεξάρτητες επιλογές.

Διατύπωση: Αν μια εργασία αποτελείται από δύο διαδοχικά βήματα, το πρώτο μπορεί να γίνει με $m$ τρόπους ΚΑΙ για καθένα από αυτούς το δεύτερο μπορεί να γίνει με $n$ τρόπους, τότε η συνολική εργασία μπορεί να γίνει με:

$$m \times n \text{ τρόπους}$$

Γενίκευση: Για $k$ διαδοχικά βήματα με $n_1, n_2, ..., n_k$ επιλογές:

$$n_1 \times n_2 \times ... \times n_k = \prod_{i=1}^{k} n_i \text{ τρόπους}$$

Παράδειγμα Εφαρμογής

Για τη δημιουργία κωδικού από 2 γράμματα και 3 ψηφία:

• Γράμματα: 24 επιλογές ανά θέση (ελληνικό αλφάβητο)
• Ψηφία: 10 επιλογές ανά θέση (0-9)

$$24 \times 24 \times 10 \times 10 \times 10 = 24^2 \times 10^3 = 576000 \text{ κωδικοί}$$

Συνδυασμός των Αρχών

Συχνά τα προβλήματα απαιτούν τον συνδυασμό και των δύο αρχών.

Παράδειγμα: Πόσοι τριψήφιοι αριθμοί υπάρχουν που αρχίζουν από 2 ή 5 και τελειώνουν σε 0;

• Πρώτο ψηφίο: 2 επιλογές (2 ή 5)
• Δεύτερο ψηφίο: 10 επιλογές (0-9)
• Τρίτο ψηφίο: 1 επιλογή (0)

$$2 \times 10 \times 1 = 20 \text{ αριθμοί}$$

Αρχή Συμπληρώματος

Αν είναι δύσκολο να μετρήσουμε άμεσα τα στοιχεία ενός συνόλου $A$, μπορούμε να χρησιμοποιήσουμε:

$$|A| = |S| - |A^c|$$

όπου $S$ είναι το σύμπαν και $A^c$ το συμπλήρωμα του $A$.

Παράδειγμα: Πόσοι τετραψήφιοι αριθμοί έχουν τουλάχιστον ένα ψηφίο 5;

• Όλοι οι τετραψήφιοι: $9 \times 10^3 = 9000$
• Χωρίς κανένα 5: $8 \times 9^3 = 5832$
• Με τουλάχιστον ένα 5: $9000 - 5832 = 3168$

Αρχή Διχοτόμησης

Όταν τα στοιχεία ενός συνόλου χωρίζονται σε δύο κατηγορίες:

$$|S| = |A| + |B|, \quad A \cap B = \emptyset$$

Αρχή της Αντιστοιχίας (Bijection)

Αν μπορούμε να δημιουργήσουμε μια αμφιμονοσήμαντη αντιστοιχία (1-1 και επί) μεταξύ δύο συνόλων $A$ και $B$, τότε:

$$|A| = |B|$$

Αυτή η αρχή είναι χρήσιμη όταν ένα σύνολο είναι πιο εύκολο να μετρηθεί από το άλλο.