Βασική αρχή απαρίθμησης

Στη συνδυαστική, η βασική αρχή απαρίθμησης (ή πολλαπλασιαστική αρχή ή αρχή του γινομένου) αναφέρεται στην εξής πρόταση: Αν μια διαδικασία μπορεί να χωριστεί σε $k$ διαδοχικές φάσεις έτσι ώστε η πρώτη φάση να μπορεί να εκτελεστεί με $n_1$ τρόπους, η δεύτερη φάση με $n_2$ τρόπους, ..., $k$-οστή φάση με $n_k$ τρόπους, τότε, η διαδικασία αυτή μπορεί να εκτελεστεί συνολικά με $n_1\cdot \dots \cdot n_k$ τρόπους.

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

Παραδείγματα

Όλοι οι τρόποι ένδυσης αν έχουμε 2 ζευγάρια παπούτσια, 4 παντελόνια και 2 μπλούζες.

• Αν έχουμε 2 ζευγάρια παπούτσια, 4 παντελόνια και 2 μπλούζες στην ντουλάπα μας, τότε υπάρχουν $2\cdot 4\cdot 2=16$ τρόποι για να διαλέξουμε τι θα φορέσουμε.
• Σε ένα τμήμα με 16 κορίτσια και 14 αγόρια, υπάρχουν $16\cdot 14=224$ τρόποι να διαλέξουμε έναν εκπρόσωπο για τα αγόρια και έναν για τα κορίτσια.
• Σε ένα πρωτάθλημα υπάρχουν 4 ομάδες. Υπάρχουν $4\cdot 3\cdot 2\cdot 1=24$ πιθανές κατατάξεις για τις ομάδες, καθώς υπάρχουν $4$ τρόποι να διαλέξουμε την πρώτη, $3$ να διαλέξουμε την δεύτερη (όλες εκτός από την πρώτη), $2$ για την τρίτη (όλες εκτός από τις δύο πρώτες) και μόνο μία για την τελευταία. Γενικεύοντας αυτό το παράδειγμα μπορούμε να δείξουμε ότι το πλήθος των μεταθέσεων $n$ στοιχείων είναι $n\cdot (n-1)\cdot \dots \cdot 2\cdot 1$.
• Ένα μαγειρείο φτιάχνει ένα από τα εξής τρία γεύματα κάθε μέρα: μακαρόνια, κοτόπουλο και ψάρι. Για μία εβδομάδα υπάρχουν συνολικά

$\underset{7\text{ γεύματα}}{\underbrace{3\cdot 3\dots \cdot 3}}=3^7$

δυνατά προγράμματα. Γενικεύοντας αυτό το παράδειγμα μπορούμε να δείξουμε ότι το πλήθος των δυνατών διατάξεων με επανάληψη $n$ στοιχείων ανά $k$ είναι $n^k$.

Δείτε επίσης

• Προσθετική αρχή απαρίθμησης
• Συνδυασμός (μαθηματικά)
• Διάταξη
• Διάταξη με επανάληψη
• Μετάθεση (μαθηματικά)