Μεταθέσεις και Διατάξεις

Με πόσους τρόπους μπορούμε να τοποθετήσουμε n διαφορετικά αντικείμενα σε n διαφορετικές αριθμημένες θέσεις με την προϋπόθεση ότι μία θέση μπορεί να χωρέσει μόνο ένα αντικείμενο;

Για το πρώτο αντικείμενο έχουμε n επιλογές θέσεων, για το δεύτερο αντικείμενο υπάρχουν n-1 επιλογές ελεύθερων θέσεων, … , και για το τελευταίο αντικείμενο υπάρχει 1 τελευταία κενή θέση.

Συνεπώς υπάρχουν n(n-1)(n-2)1 διαφορετικές ΜΕΤΑΘΕΣΕΙΣ. Το γινόμενο το ονομάζουμε n-παραγοντικό και το συμβολίζουμε με το σύμβολο n!

Άρα το πλήθος των μεταθέσεων n αντικειμένων είναι:

n!= 1x2x3xxn

Με πόσους τρόπους μπορούμε να τοποθετήσουμε k διαφορετικά αντικείμενα σε n διαφορετικά αριθμημένες θέσεις με την προϋπόθεση ότι μία θέση μπορεί να χωρέσει μόνο ένα αντικείμενο;

Για το πρώτο αντικείμενο έχουμε n επιλογές θέσεων, για το δεύτερο αντικείμενο υπάρχουν n-1 επιλογές ελεύθερων θέσεων, … , και για το k αντικείμενο υπάρχουν (n-k+1) ελεύθερες θέσεις.

Συνεπώς υπάρχουν n(n-1)(n-2)(n-k+1) διαφορετικές ΔΙΑΤΑΞΕΙΣ των k από n αντικείμενα. Για το γινόμενο αυτό χρησιμοποιούμε το σύμβολο P(n, k)

 

Γενικότερα τα προβλήματα τέτοιας μορφής μπορούμε να τα θεωρήσουμε ως παραλλαγές του παρακάτω προβλήματος:

Έστω ότι θέλουμε να τοποθετήσουμε k διαφορετικά βαμμένες μπάλες σε n διαφορετικά αριθμημένα κουτιά με την προϋπόθεση ότι ένα κουτί μπορεί να χωρέσει μόνο μία μπάλα. Η απάντηση σε αυτό το πρόβλημα δίνεται από το τύπο:

P(n, k)=n(n-1)(n-2)(n-k+1)

Σημειώνουμε ότι για κάθε αριθμό b¹ 0 ισχύει a= axb/b. Άρα ισχύουν τα παρακάτω:

P(n, k)=n(n-1)(n-2)(n-k+1) =

= n(n-1)(n-2)(n-k+1)(n-k)(n-k-1)2.1/(n-k)(n-k-1)2.1 =

= n!/(n-k)!

Άρα το πλήθος των διατάξεων των k από n αντικείμενα είναι:

P(n, k)= n!/(n-k)!

Παράδειγμα: Με πόσους τρόπους μπορούν να καθίσουν 4 φοιτητές σε 7 θέσεις;

Ο πρώτος φοιτητής μπορεί να καθίσει σε οποιαδήποτε από τις 7 θέσεις, ο δεύτερος σε οποιαδήποτε από τις υπόλοιπες 6 θέσεις, ο τρίτος φοιτητής σε οποιαδήποτε από τις υπόλοιπες 5 θέσεις και ο τέταρτος φοιτητής σε οποιαδήποτε από τις υπόλοιπες 4 θέσεις.

Συνεπώς ο συνολικός τρόπος με το οποίο μπορούν να καθίσουν k φοιτητές σε n θέσεις είναι:

P(7, 4)=7x6x5x4=840.

Παράδειγμα: Με πόσους τρόπους είναι δυνατόν να προγραμματιστούν τρία διαγωνίσματα σε μία περίοδο πέντε ημερών, έτσι ώστε να μην έχουν προγραμματιστεί δύο διαγωνίσματα για την ίδια ημέρα;

Θεωρώντας τα διαγωνίσματα ως διαφορετικές μπάλες και τις ημέρες ως αριθμημένα κουτιά παίρνουμε το αποτέλεσμα P(5,3)=5x4x3=60.

Ένα ισοδύναμο πρόβλημα με το να τοποθετήσουμε μπάλες σε κουτιά είναι αυτό της διάταξης διακριτών αντικειμένων. Όταν λέμε ότι διατάσσουμε k από n διακριτά αντικείμενα εννοούμε ότι επιλέγουμε k από τα n αντικείμενα με κάποια σειρά. Η διάταξη k από n αντικείμενα ανάγεται στην πλήρωση k θέσεων με k από τα n διακριτά αντικείμενα.

Για τη πρώτη θέση υπάρχουν n επιλογές αντικειμένων, για τη δεύτερη θέση υπάρχουν n-1 επιλογές αντικειμένων (από τα υπόλοιπα n-1 αντικείμενα), … , και για τη k θέση υπάρχουν n-k+1 επιλογές (από τα n-k+1 υπόλοιπα αντικείμενα). Συνεπώς υπάρχουν P(n, k) τρόποι για τη διάταξη k από τα n αντικείμενα.

Παράδειγμα: Με πόσους τρόπους μπορούμε να σχηματίσουμε συμβολοσειρές από τέσσερα διαφορετικά γράμματα;

Το πρόβλημα αποτελεί ένα πρόβλημα διάταξης 4 από 24 αντικείμενα. Για τη πρώτη θέση υπάρχουν 24 επιλογές γραμμάτων, για τη δεύτερη θέση υπάρχουν 23 επιλογές γραμμάτων (από τα υπόλοιπα 23 γράμματα), για τη τρίτη θέση υπάρχουν 22 επιλογές γραμμάτων (από τα υπόλοιπα 22 γράμματα), και για τη τέταρτη θέση υπάρχουν 21 επιλογές (από τα υπόλοιπα 21 γράμματα). Άρα ο συνολικός αριθμός των διαφορετικών συμβολοσειρών με τέσσερα διαφορετικά γράμματα είναι P(24,4)=24x23x22x21=255024.

Παράδειγμα:

(α) Υποθέστε ότι δεν επιτρέπονται επαναλήψεις. Πόσοι τετραψήφιοι αριθμοί είναι δυνατόν να σχηματιστούν από τα ψηφία 1, 2, 3, 5, 7, 8;

Η συγκεκριμένη περίπτωση αποτελεί πρόβλημα διάταξης 4 από 6 αντικείμενα. Άρα η λύση είναι:

P(n,k)=n(n-1)(n-2)(n-k+1)

Επομένως P(6,4)=6x5x4x3=360

(β) Πόσοι από τους παραπάνω αριθμούς είναι μικρότεροι από 4000;

Ένας τετραψήφιος αριθμός είναι μικρότερος από 4000 όταν το πρώτο ψηφίο του είναι μικρότερο του 4. Άρα θα πρέπει πρώτα να τοποθετήσουμε στη θέση του πρώτου ψηφίου ένα από τους αριθμούς 1, 2, και 3 και στη συνέχεια να τοποθετήσουμε τους υπόλοιπους αριθμούς στις θέσεις των υπόλοιπων ψηφίων. Θα λύσουμε το πρόβλημα σε δύο φάσεις.

Στην πρώτη φάση τίθεται το ερώτημα: "Με πόσους τρόπους μπορούμε να τοποθετήσουμε έναν από τους αριθμούς 1, 2, 3 στη μία θέση;" Η προφανής απάντηση είναι P(3,1)=3.

Στη δεύτερη φάση τίθεται το ερώτημα: "Με πόσους τρόπους μπορούμε να τοποθετήσουμε τους υπόλοιπους αριθμούς στις τρεις υπόλοιπες θέσεις;" Η απάντηση είναι P(5,3)=5x4x3=60.

Σύμφωνα με το κανόνα του γινομένου υπάρχουν 3x60=180 αριθμοί μικρότεροι του 4000.

(γ) Πόσοι από τους αριθμούς του (α) είναι άρτιοι;

Ένας αριθμός είναι άρτιος (διαιρείται με το 2) όταν το τελευταίο ψηφίο του διαιρείται με το 2. Άρα θα πρέπει πρώτα να τοποθετήσουμε στη θέση του τελευταίου ψηφίου ένα από τους αριθμούς 2, και 8 και στη συνέχεια να τοποθετήσουμε τους υπόλοιπους αριθμούς στις θέσεις των υπόλοιπων ψηφίων. Θα λύσουμε το πρόβλημα σε δύο φάσεις:

Στην πρώτη φάση τίθεται το ερώτημα: "Με πόσους τρόπους μπορούμε να τοποθετήσουμε έναν από τους αριθμούς 2 και 8 στη μία θέση;" Η προφανής απάντηση είναι P(2,1)=2.

Στη δεύτερη φάση τίθεται το ερώτημα: "Με πόσους τρόπους μπορούμε να τοποθετήσουμε τους υπόλοιπους αριθμούς στις τρεις υπόλοιπες θέσεις;" Η απάντηση είναι P(5,3)=5x4x3=60.

Σύμφωνα με το κανόνα του γινομένου υπάρχουν 2x60=120 άρτιοι αριθμοί.

 (δ) Πόσοι από τους αριθμούς του (α) διαιρούνται με το 5;

Ένας αριθμός διαιρείται με το 5 όταν το τελευταίο ψηφίο του είναι 0 ή 5.

Άρα θα πρέπει υποχρεωτικά να τοποθετήσουμε στη θέση του τελευταίου ψηφίου τον αριθμό 5 και στη συνέχεια να τοποθετήσουμε τους υπόλοιπους αριθμούς στις θέσεις των υπόλοιπων ψηφίων.

Συνεπώς το πρόβλημα ανάγεται στο παρακάτω: "Με πόσους τρόπους μπορούμε να τοποθετήσουμε τους υπόλοιπους αριθμούς στις τρεις υπόλοιπες θέσεις;" Η απάντηση είναι P(5,3)=5x4x3=60.