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

Στη συνδυαστική, η βασική αρχή απαρίθμησης (ή πολλαπλασιαστική αρχή ή αρχή του γινομένου) αναφέρεται στην εξής πρόταση:^[1]^[2]^[3]^[4] Αν μια διαδικασία μπορεί να χωριστεί σε $k$ διαδοχικές φάσεις έτσι ώστε η πρώτη φάση να μπορεί να εκτελεστεί με $n_{1}$ τρόπους, η δεύτερη φάση με $n_{2}$ τρόπους, ..., $k$ -οστή φάση με $n_{k}$ τρόπους, τότε, η διαδικασία αυτή μπορεί να εκτελεστεί συνολικά με $n_{1}\cdot \ldots \cdot n_{k}$ τρόπους.

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

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

Αν έχουμε 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 \ldots \cdot 2\cdot 1$ .
Ένα μαγειρείο φτιάχνει ένα από τα εξής τρία γεύματα κάθε μέρα: μακαρόνια, κοτόπουλο και ψάρι. Για μία εβδομάδα υπάρχουν συνολικά

\underbrace {3\cdot 3\ldots \cdot 3} _{7{\text{ γεύματα}}}=3^{7}

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

n

στοιχείων ανά

k

είναι

n^{k}

.

Δείτε επίσης

Πηγές

↑ Mωυσιάδης, Πολυχρόνης Θ. «Αρχές Απαρίθμησης» (PDF). Τμήμα Μαθηματικών ΑΠΘ. Ανακτήθηκε στις 11 Φεβρουαρίου 2023.
↑ Καφεσάκη, Μαρία. «Βασική Αρχή Απαρίθμησης». Ανακτήθηκε στις 11 Φεβρουαρίου 2023.
↑ Μακρής, Γεώργιος Χρ. «Διακριτά Μαθηματικά Συνδυαστική» (PDF). Ανακτήθηκε στις 11 Φεβρουαρίου 2023.
↑ Παπαδόπουλος, Γεώργιος. «Πώς απαριθμούμε;» (PDF). Τμήμα Επιστήμης Φυτικής Παραγωγής. Ανακτήθηκε στις 11 Φεβρουαρίου 2023.

[1] Mωυσιάδης, Πολυχρόνης Θ. «Αρχές Απαρίθμησης» (PDF). Τμήμα Μαθηματικών ΑΠΘ. Ανακτήθηκε στις 11 Φεβρουαρίου 2023.

[2] Καφεσάκη, Μαρία. «Βασική Αρχή Απαρίθμησης». Ανακτήθηκε στις 11 Φεβρουαρίου 2023.

[3] Μακρής, Γεώργιος Χρ. «Διακριτά Μαθηματικά Συνδυαστική» (PDF). Ανακτήθηκε στις 11 Φεβρουαρίου 2023.

[4] Παπαδόπουλος, Γεώργιος. «Πώς απαριθμούμε;» (PDF). Τμήμα Επιστήμης Φυτικής Παραγωγής. Ανακτήθηκε στις 11 Φεβρουαρίου 2023.

[1]

[2]

[3]

[4]