Βασικά ζήτημα στα Διακριτά Μαθηματικά και στην Συνδυαστική είναι η μέτρηση των διακριτών δομών που προκύπτουν μέσα από διάφορες διαδικασίες κατασκευής. Προβλήματα απαρίθμησης, χρωματισμού, υπολογισμού συνδυασμών μεταθέσεων και διατάξεων αντικειμένων αποτελούν τον χώρο μελέτης της Συνδυαστικής.
Ένα παράδειγμα είναι το ακόλουθο:
Σας δίνω τα 10 ψηφία του δεκαδικού συστήματος αρίθμησης: τα ψηφία από το 0 έως και το 9. Επίσης, σας δίνω τα 24 γράμματα του ελληνικού αλφάβητου στα κεφαλαία: από το Α έως και το Ω. Το ερώτημα είναι το εξής:
"Πόσα ζευγάρια (αριθμός, γράμμα) μπορούμε να κατασκευάσουμε;"
Εδώ οι διακριτές δομές είναι τα ζευγάρια (αριθμός, γράμμα) ενώ η διαδικασία κατασκευής των δομών αυτών είναι το ζευγάρωμα ενός από τα ψηφία 0 έως 9 με ένα από τα γράμματα Α έως Ω. Η διαίσθησή μας, τώρα, θα μας έλεγε ότι πρέπει να υπάρχουν 10x24 τέτοια ζευγάρια, καθώς για καθένα από τα 10 ψηφία υπάρχουν 24 γράμματα με τα οποία μπορεί να γίνει το ζευγάρωμα.
Μέσα από το παράδειγμα αυτό προκύπτει και μια σημαντική διαφοροποίηση υπολογισμού.
Αναφερόμαστε σε διακριτές δομές δηλαδή σε ανόμοια στοιχεία,(αριθμοί και γράμματα) και όχι σε μη- διακριτά. Ας δώσουμε τους βασικούς κανόνες,
Κανόνας Γινομένου
Εάν ένα ενδεχόμενο μπορεί να πραγματοποιηθεί με m διαφορετικούς τρόπους ενώ ένα άλλο, ανεξάρτητο, ενδεχόμενο μπορεί να πραγματοποιηθεί με n τρόπους τότε ο συνδυασμός των δύο ενδεχομένων μπορεί να πραγματοποιηθεί με mxn τρόπους.Ο κανόνας ισχύει και για περισσότερα των δύο ανεξάρτητων ενδεχόμενων.
Για παράδειγμα, "Πόσοι δυαδικοί αριθμοί υπάρχουν με 8bits;" φυσικά 256, αφού κάθε θέση από τις οκτώ μπορεί να καλυφτεί με 2 bit 0 ή 1 τότε 2x2x2x2x2x2x2x2=256.
Κανόνας Αθροίσματος
Εάν ένα ενδεχόμενο μπορεί να πραγματοποιηθεί με m διαφορετικούς τρόπους ενώ ένα άλλο ενδεχόμενο μπορεί να πραγματοποιηθεί με n τρόπους, και τα δύο ενδεχόμενα δεν μπορεί να πραγματοποιηθούν ταυτόχρονα, δηλαδή είναι αμοιβαία αποκλειόμενα, τότε η πραγματοποίηση κάποιου από τα δύο αυτά ενδεχόμενα μπορεί να γίνει με m+n διαφορετικούς τρόπους.
Ο ίδιος κανόνας γενικεύεται και για περισσότερα από δύο αμοιβαία αποκλειόμενα ενδεχόμενα.
"Σε έκθεση αυτοκινήτων υπάρχουν 5 διαφορετικά αυτοκίνητα του κατασκευαστή Α, 6 διαφορετικά αυτοκίνητα του κατασκευαστή B και 8 διαφορετικά αυτοκίνητα του κατασκευαστή Γ.
Ο υπεύθυνος της έκθεσης θέλει να επιλέξει ένα ζεύγος αυτοκινήτων διαφορετικών κατασκευαστών.
Με πόσους τρόπους μπορεί να γίνει αυτό;"
Έχουμε τρεις τρόπους να επιλέξουμε ένα ζεύγος αυτοκινήτων από διαφορετικούς κατασκευαστές: επιλογή από Α και Β, από Β και Γ και από Α και Γ. Η επιλογή από Α και Β μπορεί να γίνει με 5x6=30 τρόπους, από τον κανόνα του γινομένου (ανεξάρτητα ενδεχόμενα αφού είναι διαφορετικοί οι κατασκευαστές ). Ομοίως,η επιλογή από Β και Γ μπορεί να γίνει με 6x8=48 τρόπους, ενώ η επιλογή από Α και Γ μπορεί να γίνει με 5x8=40 τρόπους. Όλες αυτές οι επιλογές είναι αμοιβαία αποκλειόμενες (η επιλογή του ζεύγους κατασκευαστών Α, Β αποκλείει την επιλογή του ζεύγους Α, Γ), οπότε, από τον κανόνα του γινομένου, βρίσκουμε ότι ο αριθμός των διαφορετικών επιλογών του υπεύθυνου της έκθεσης είναι ίσος με 30+48+40=118.
Περισσότερα μπορείτε να δείτε και στις Σηµειώσεις για το µάθηµα Συνδιαστική .
Δημοσίευση σχολίου