Συνδυαστική

Θέλεις να μάθεις με πόσους διαφορετικούς τρόπους μπορείς να διαλέξεις πέντε φύλλα από μια τράπουλα 32 φύλλων; Αυτό είναι ακριβώς το είδος του προβλήματος που λύνει η συνδυαστική. Υπάρχουν δύο βασικές αρχές της συνδυαστικής – η αθροιστική και η πολλαπλασιαστική. Όλες οι άλλες μέθοδοι είναι απλώς επεκτάσεις αυτών των βασικών αρχών.

Αθροιστική αρχή

Η αθροιστική αρχή είναι πολύ απλή – λέει ότι αν έχουμε σύνολα A, B χωρίς κανένα κοινό στοιχείο, τότε ο αριθμός των τρόπων με τους οποίους μπορούμε να επιλέξουμε ένα στοιχείο από την ένωση A ∪ B είναι ίσος με |A| + |B|, δηλαδή με το άθροισμα των πληθαρίθμων των συνόλων.

Θα ξεκινήσουμε με ένα εύκολο παράδειγμα. Έχουμε 6 κόκκινες και 8 μπλε μπάλες. Τις ρίχνουμε όλες σε ένα δοχείο. Πόσες δυνατότητες έχουμε συνολικά, αν τραβήξουμε μία μπάλα; Στην αρχή είχαμε το σύνολο των κόκκινων μπαλών, που το ονομάζουμε A, και το σύνολο των μπλε μπαλών, που το ονομάζουμε B. Τα σύνολα αυτά είναι ξένα, δηλαδή δεν έχουν καμία κοινή μπάλα. Θέλουμε να τραβήξουμε μία μπάλα, άρα έχουμε συνολικά |A| + |B| = 6 + 8 = 14 δυνατότητες. Αυτό είναι όλο.

Πολλαπλασιαστική αρχή

Έχουμε πάλι δύο σύνολα, το Γ και το Α. Το σύνολο Γ περιέχει τρεις γυναίκες και το σύνολο Α τέσσερις άνδρες. Τώρα ρωτάμε: πόσα διαφορετικά ζευγάρια άνδρας − γυναίκα μπορούμε να φτιάξουμε από αυτά τα σύνολα; Αυτό που κάνουμε είναι να παίρνουμε κάθε φορά μία γυναίκα και να της αντιστοιχίζουμε έναν άνδρα. Τον αριθμό όλων των ζευγαριών τον υπολογίζουμε ως εξής: παίρνουμε μία γυναίκα, την Κατερίνα, και της αντιστοιχίζουμε διαδοχικά όλους τους άνδρες. Έτσι παίρνουμε 4 διαφορετικά ζευγάρια, γιατί μπορούμε να της αντιστοιχίσουμε συνολικά 4 διαφορετικούς άνδρες. Το ίδιο κάνουμε και για τις άλλες δύο γυναίκες, που δίνουν κι αυτές από 4 ζευγάρια. Και αυτό είναι όλο, έχουμε συνολικά 4 + 4 + 4 = 12 ζευγάρια.

Τι κάναμε στην πραγματικότητα; Πολλαπλασιάσαμε τους πληθαρίθμους των δύο συνόλων. Είχαμε 3 γυναίκες και 4 άνδρες, άρα ο συνολικός αριθμός των ζευγαριών είναι 3 · 4 = 12. Γι' αυτό λέγεται πολλαπλασιαστική αρχή. Αν λοιπόν έχουμε δύο σύνολα και φτιάχνουμε ζεύγη από αυτά, απλώς πολλαπλασιάζουμε το πλήθος των στοιχείων του ενός συνόλου με το πλήθος των στοιχείων του άλλου.

Παρακάτω μπορείς να δεις ότι αυτό πράγματι ισχύει. Ακολουθούν όλα τα ζευγάρια που μπορούμε να φτιάξουμε από 3 γυναίκες και 4 άνδρες. Κάθε γραμμή αντιπροσωπεύει τις δυνατότητες για μία από τις γυναίκες και κάθε στήλη τις δυνατότητες για έναν από τους άνδρες. Έχουμε λοιπόν τρεις γραμμές και τέσσερις στήλες, άρα συνολικά γραμμές · στήλες δυνατότητες.

$$\begin{array}{rcl}& & ({\Gamma }_1,{{\rm A}}_1),({\Gamma }_1,{{\rm A}}_2),({\Gamma }_1,{{\rm A}}_3),({\Gamma }_1,{{\rm A}}_4),\\ & & ({\Gamma }_2,{{\rm A}}_1),({\Gamma }_2,{{\rm A}}_2),({\Gamma }_2,{{\rm A}}_3),({\Gamma }_2,{{\rm A}}_4),\\ & & ({\Gamma }_3,{{\rm A}}_1),({\Gamma }_3,{{\rm A}}_2),({\Gamma }_3,{{\rm A}}_3),({\Gamma }_3,{{\rm A}}_4)\end{array}$$

Λυμένα παραδείγματα

1. Πόσοι διαφορετικοί διψήφιοι αριθμοί υπάρχουν; Πώς μοιάζει ένας διψήφιος αριθμός; Στην πρώτη θέση βρίσκεται ένα από τα ψηφία 1, …, 9, ενώ στη δεύτερη θέση μπορεί να βρίσκεται επιπλέον και το μηδέν: 0, …, 9. Στο πρώτο σύνολο έχουμε λοιπόν 9 ψηφία, στο δεύτερο 10. Χρησιμοποιούμε την πολλαπλασιαστική αρχή και παίρνουμε το τελικό αποτέλεσμα: 9 · 10 = 90.

• Πόσοι διαφορετικοί τριψήφιοι αριθμοί υπάρχουν, στους οποίους κανένα ψηφίο δεν επαναλαμβάνεται δύο φορές; Στην πρώτη θέση μπορούν πάλι να βρίσκονται εννέα ψηφία, ο αριθμός δεν μπορεί να αρχίζει από μηδέν. Στη δεύτερη θέση μπορούν να βρίσκονται όλα τα ψηφία μαζί με το μηδέν, αλλά δεν επιτρέπεται να βρίσκεται το ψηφίο που υπάρχει στην πρώτη θέση, οπότε από τα δέκα δυνατά ψηφία αφαιρούμε ένα (για παράδειγμα, αν ο τριψήφιος αριθμός μας αρχίζει από το τέσσερα, είναι φανερό ότι στη δεύτερη θέση δεν μπορεί να υπάρχει πάλι το τέσσερα, γιατί θα υπήρχε δύο φορές σε όλον τον αριθμό). Στην τρίτη θέση μπορούν πάλι να βρίσκονται όλα τα ψηφία, αλλά όχι εκείνο που βρίσκεται στην πρώτη ή στη δεύτερη θέση. Ο λόγος είναι πάλι ο ίδιος. Αν στην πρώτη θέση είναι το ψηφίο 4 και στη δεύτερη το 7, τότε στην τρίτη θέση μπορούμε να βάλουμε ένα ψηφίο από το {0, …, 9} ∖ {4, 7}. Από τα δέκα ψηφία πρέπει να αφαιρέσουμε δύο. Τώρα απλώς πολλαπλασιάζουμε: 9 · 9 · 8 = 648. Συνολικά υπάρχουν λοιπόν 648 τέτοιοι αριθμοί.
• Ρίχνουμε ένα συνηθισμένο ζάρι δύο φορές στη σειρά. Πόσα διαφορετικά αποτελέσματα μπορούμε να πάρουμε; Στην πρώτη ρίψη μπορούν να έρθουν 6 διαφορετικά αποτελέσματα. Στη δεύτερη επίσης, άρα ο συνολικός αριθμός δυνατοτήτων είναι 6 · 6 = 36.
• Ρίχνουμε ένα ζάρι δύο φορές στη σειρά. Πόσα διαφορετικά αποτελέσματα μπορούμε να πάρουμε, αν στην πρώτη ρίψη ήρθε άρτιος αριθμός; Στην πρώτη ρίψη ήρθε άρτιος αριθμός, δηλαδή ένας από τους 2, 4, 6, που είναι συνολικά 3 δυνατότητες. Στη δεύτερη ρίψη μπορεί να έρθει οποιοσδήποτε αριθμός, άρα συνολικά έχουμε 3 · 6 = 18 δυνατότητες.