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

Αυτή είναι η σύντομη έκδοση.

Ας πάρουμε για παράδειγμα ένα κουδούνισμα σε μια εκκλησία.

Μια παραλλαγή είναι μια σειρά των κουδουνιών. Αναζητάτε την καλύτερη σειρά για να τους καλέσετε.

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

Αυτό δημιουργεί τη γνωστή ταυτότητα: (n P r) = (n C r) * r!

Ο τρόπος για να σειρά rστοιχείων από nείναι να επιλέξετε πρώτα rστοιχεία από n, και στη συνέχεια να παραγγείλετε τα rστοιχεία ( r!)

Και αυτό σημαίνει (n P r) = n! / (n-r)!και(n C r) = n! / ( (n-r)! * r! )

Αλλά θέλεις να μάθεις πώς να το θυμάσαι για πάντα;

Είμαι οπαδός της σκέψης των πρώτων αρχών. Για να καταλάβετε ένα πρόβλημα, μεταβείτε στον πυρήνα του και συλλογιστείτε από εκεί

Το να μην το κάνω αυτό είναι συνήθως η πηγή σύγχυσης: εάν δεν καταλαβαίνω πώς λειτουργούν τα πράγματα, δεν ξέρω πού να κρεμάσω τις έννοιες. Το διανοητικό μου πλαίσιο δεν είναι πλήρες, γι 'αυτό αποφασίζω να το θυμηθώ.

Όπως μπορείτε να φανταστείτε, αυτό δεν είναι ιδανικό. Έτσι, από καιρό σε καιρό, επιδοκιμάζομαι σε μια άσκηση να αντλήσω πράγματα από την πηγή και να δημιουργήσω τη διαίσθηση για το πώς λειτουργούν τα πράγματα.

Αυτή τη φορά, χτίζουμε διαίσθηση για παραλλαγές και συνδυασμούς.

Για παράδειγμα, γνωρίζετε γιατί ο τύπος ενός συνδυασμού είναι (n C r); Από που προήλθε αυτό; Και γιατί χρησιμοποιούνται τα παραγοντικά εδώ;

Ας ξεκινήσουμε από την πηγή. Factorials, Permutations και συνδυασμοί γεννήθηκαν από μαθηματικούς που παίζουν μαζί, σαν τον τρόπο με τον οποίο ο Steve Jobs και ο Steve Wozniak ίδρυσαν την Apple παίζοντας μαζί στο γκαράζ τους.

Ακριβώς όπως το πώς η Apple έγινε μια πλήρης κερδοφόρα εταιρεία, το απλό παραγοντικό !, έγινε το άτομο ενός ολόκληρου πεδίου μαθηματικών: συνδυαστικών.

Ξεχάστε τα πάντα, ας αρχίσουμε να σκεφτόμαστε από κάτω προς τα πάνω.

Η πρώτη γνωστή ενδιαφέρουσα περίπτωση χρήσης προήλθε από Εκκλησίες τον 17ο αιώνα.

Αναρωτηθήκατε πώς κουδουνίζουν οι εκκλησίες στις εκκλησίες; Υπάρχει μια μηχανή που τα "χτυπά" στη σειρά. Αλλάξαμε σε μηχανήματα επειδή τα κουδούνια είναι πολύ μεγάλα. Επίσης, υπάρχουν τόνοι κουδουνιών.

Πώς βρήκαν οι άνθρωποι την καλύτερη ακολουθία για να τους χτυπήσουν; Τι γίνεται αν ήθελαν να αλλάξουν τα πράγματα; Πώς θα μπορούσαν να βρουν τον καλύτερο ήχο; Κάθε καμπαναριό είχε έως και 16 κουδούνια!

Δεν μπορούσες να αλλάξεις πόσο γρήγορα μπορούσες να χτυπήσεις ένα κουδούνι - οι μηχανές χτυπούσαν μόνο ένα κουδούνι κάθε δευτερόλεπτο. Το μόνο πράγμα που μπορούσατε να κάνετε ήταν να αλλάξετε τη σειρά των κουδουνιών. Έτσι, αυτή η πρόκληση ήταν να βρούμε την καλύτερη σειρά.

Θα μπορούσαμε, στο δρόμο, να ανακαλύψουμε όλες τις πιθανές παραγγελίες; Θέλουμε να μάθουμε όλες τις πιθανές παραγγελίες για να καταλάβουμε αν αξίζει να τις δοκιμάσουμε όλες.

Ένας κουδούνι, ο Fabian Stedman ανέλαβε αυτήν την πρόκληση.

Ξεκίνησε με 2 κουδούνια. Σε ποιες διαφορετικές παραγγελίες μπορούσε να χτυπήσει αυτά τα κουδούνια; [1]

1 και 2.

ή

2 και 1.

Αυτό είχε νόημα. Δεν υπήρχε άλλος τρόπος.

Τι γίνεται με 3 κουδούνια;

1, 2 και 3.

1, 3 και 2.

Στη συνέχεια ξεκινώντας με το δεύτερο κουδούνι,

2, 1 και 3.

2, 3 και 1.

Στη συνέχεια ξεκινώντας με το τρίτο κουδούνι,

3, 1 και 2.

3, 2 και 1.

Σύνολο, 6.

Συνειδητοποίησε τότε ότι ήταν πολύ παρόμοιο με δύο καμπάνες!

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

Πόσοι τρόποι θα μπορούσε να διορθώσει το πρώτο κουδούνι; Οποιοδήποτε από τα 3 κουδούνια θα μπορούσε να είναι το ένα!

Εντάξει, συνέχισε. Έφτασε τότε 5 καμπάνες.

Αυτό είναι όταν συνειδητοποίησε ότι το να κάνεις πράγματα με το χέρι είναι δύσκολο. Έχετε μόνο τόσο πολύ χρόνο στην ημέρα, πρέπει να χτυπάτε κουδούνια, δεν μπορείτε να κολλήσετε αντλώντας όλες τις πιθανές καμπάνες. Υπήρχε τρόπος να το καταλάβω γρήγορα;

Επέστρεψε στην αντίληψή του.

Αν είχε 5 κουδούνια και έβαζε το πρώτο κουδούνι, το μόνο που έπρεπε να κάνει ήταν να βρει πώς να παραγγείλει 4 κουδούνια.

Για 4 κουδούνια; Λοιπόν, αν είχε 4 κουδούνια και έφτιαξε το πρώτο κουδούνι, το μόνο που έπρεπε να κάνει ήταν να βρει πώς να παραγγείλει 3 κουδούνια.

Και ήξερε πώς να το κάνει αυτό!

Έτσι, παραγγελία 5 κουδουνιών = 5 * παραγγελία 4 κουδουνιών.

Παραγγελία 4 κουδουνιών = 4 * παραγγελία 3 κουδουνιών

Παραγγελία 3 κουδουνιών = 3 * παραγγελία 2 κουδουνιών.

.. Βλέπετε το μοτίβο, έτσι δεν είναι;

Fun Fact: Αυτό είναι το κλειδί για μια τεχνική προγραμματισμού που ονομάζεται recursion.

Και το έκανε. Παρόλο που τον πήρε πολύ περισσότερο, καθώς κανείς κοντά του δεν το είχε ανακαλύψει ήδη. [2]

Έτσι, κατάλαβε ότι η σειρά των 5 κουδουνιών = 5 * 4 * 3 * 2 * 1.

Αυτός ο τύπος παραγγελίας, το 1808, έγινε γνωστός ως παραγοντικός.

Πιστεύουμε ότι η παραγοντική σημειογραφία είναι η βάση, αλλά η ιδέα υπήρχε πολύ πριν είχε ένα όνομα. Μόνο όταν ο Γάλλος μαθηματικός Christian Kramp παρατήρησε ότι χρησιμοποιείται σε μερικά μέρη το ονόμασε ως παραγοντικό.

Αυτή η σειρά κουδουνιών ονομάζεται παραλλαγή.

Η παραλλαγή είναι μια σειρά αντικειμένων.

Όταν μαθαίνω κάτι, νομίζω ότι βοηθάει να κοιτάμε τα πράγματα από κάθε διαφορετική γωνία, για να σταθεροποιήσουμε την κατανόηση.

Τι γίνεται αν προσπαθήσουμε να αντλήσουμε τον παραπάνω τύπο απευθείας, χωρίς να προσπαθήσουμε να μειώσουμε το πρόβλημα σε μικρότερο αριθμό κουδουνιών;

Έχουμε 5 χώρους, σωστά;

Πόσοι τρόποι μπορούμε να επιλέξουμε το πρώτο κουδούνι; 5, γιατί αυτός είναι ο αριθμός των κουδουνιών που έχουμε.

Το δεύτερο κουδούνι; Λοιπόν, εξαντλήσαμε ένα κουδούνι όταν το τοποθετήσαμε στην πρώτη θέση, οπότε έχουμε 4 καμπάνες.

Το τρίτο κουδούνι; Λοιπόν, έχουμε επιλέξει τα δύο πρώτα, οπότε απομένουν μόνο 3 καμπάνες για να διαλέξετε.

Το τέταρτο κουδούνι; Απομένουν μόνο 2 καμπάνες, οπότε 2 επιλογές.

Το πέμπτο κουδούνι; Απομένει μόνο 1, οπότε 1 επιλογή.

Και εκεί το έχουμε, ο συνολικός αριθμός παραγγελιών είναι 5 * 4 * 3 * 2 * 1

Έτσι, έχουμε τον πρώτο γενικό τύπο μας.

Ο αριθμός των τρόπων παραγγελίας Nαντικειμένων είναι N!

Η παραλλαγή

Τώρα, είμαστε αντιμέτωποι με ένα διαφορετικό πρόβλημα. Ο βασιλιάς διέταξε να γίνουν νέες καμπάνες για κάθε εκκλησία. Μερικά είναι ωραία, μερικά είναι εντάξει, μερικά θα σας κάνουν να κωφούς. Αλλά όλα είναι μοναδικά. Ο καθένας κάνει το δικό του ήχο. Ένα εκκωφαντικό κουδούνι που περιβάλλεται από ωραία κουδούνια μπορεί να ακούγεται μαγευτικό.

Όμως, ο καμπαναριό μας διατηρεί ακόμα 5 καμπάνες, οπότε πρέπει να καταλάβουμε την καλύτερη παραγγελία από 8 καμπάνες που έκαναν οι εξειδικευμένοι κατασκευαστές κουδουνιών

Χρησιμοποιώντας την παραπάνω λογική, μπορούμε να προχωρήσουμε.

Για το πρώτο κουδούνι, μπορούμε να επιλέξουμε οποιοδήποτε από τα 8 κουδούνια.

Για το δεύτερο κουδούνι, μπορούμε να επιλέξουμε οποιοδήποτε από τα υπόλοιπα 7 κουδούνια ... και ούτω καθεξής.

Στο τέλος, λαμβάνουμε 8 * 7 * 6 * 5 * 4πιθανές παραγγελίες 8 κουδουνιών σε 5 χώρους.

Εάν είστε εξοικειωμένοι με την έκδοση τύπου (n P r), που είναι n! / (n-r)!, μην ανησυχείτε, θα προκύψουμε και αυτό σύντομα!

Ένας κακός τρόπος για να το αντλήσετε είναι να πολλαπλασιάσετε τον αριθμητή και τον παρονομαστή με το 3! στο παραπάνω παράδειγμά μας -

παίρνουμε 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 / 3 * 2 * 1= 8! / 3!.

Αλλά αυτό δεν μας βοηθά να καταλάβουμε γιατί λειτουργεί αυτός ο τύπος. Πριν φτάσουμε εκεί, ας ρίξουμε μια ματιά στην επιλογή των πραγμάτων, ή του Συνδυασμού.

Ο συνδυασμός

Τώρα που ξέρουμε πώς να παραγγέλνουμε πράγματα, μπορούμε να καταλάβουμε πώς να επιλέξουμε πράγματα!

Ας εξετάσουμε το ίδιο πρόβλημα. Υπάρχει ένα καμπαναριό με 5 κουδούνια και έχετε 8 κουδούνια. Ωστόσο, αυτή τη στιγμή, δεν θέλετε να καταλάβετε τη σειρά των κουδουνιών (θυμηθείτε ότι είναι αυτή η παραλλαγή).

Αντ 'αυτού, θέλετε να επιλέξετε τα 5 καλύτερα κουδούνια και να αφήσετε κάποιον άλλο με καλύτερη γεύση στη μουσική να καταλάβει την παραγγελία. Στην πραγματικότητα, διασπάμε το πρόβλημα σε μέρη: Πρώτον, καταλαβαίνουμε ποια καμπάνα να επιλέξουμε. Στη συνέχεια, καταλαβαίνουμε πώς να παραγγείλετε τα επιλεγμένα κουδούνια.

Πώς επιλέγετε τα κουδούνια; Αυτός είναι ο «συνδυασμός» από παραλλαγές και συνδυασμούς.

Ο συνδυασμός είναι μια επιλογή. Είστε επιλεκτικοί. Επιλέγετε 5 καμπάνες από 8 που έχουν φτιάξει οι τεχνίτες σας.

Εφόσον γνωρίζουμε πώς να παραγγέλνουμε καμπάνες, θα χρησιμοποιήσουμε αυτές τις πληροφορίες για να καταλάβουμε πώς να επιλέγουμε καμπάνες. Ακούγεται αδύνατο; Περιμένετε μέχρι να δείτε τα όμορφα μαθηματικά.

Ας φανταστούμε ότι όλα τα κουδούνια είναι στη σειρά.

Πριν βρούμε όλους τους τρόπους για να επιλέξετε κουδούνια, ας επικεντρωθούμε σε έναν τρόπο για να επιλέξετε κουδούνια.

Ένας τρόπος είναι να επιλέξετε οποιαδήποτε τυχαία 5. Αυτό δεν μας βοηθά να λύσουμε το πρόβλημα πολύ, οπότε ας δοκιμάσουμε έναν άλλο τρόπο.

Βάζουμε τα κουδούνια σε μια σειρά και επιλέγουμε τα πρώτα 5. Αυτός είναι ένας τρόπος για να επιλέξετε τα κουδούνια.

Παρατηρήστε ότι, ακόμη και αν αλλάξουμε θέσεις των πρώτων 5 κουδουνιών, η επιλογή δεν αλλάζει. Εξακολουθούν να είναι ο ίδιος τρόπος για να επιλέξετε 5 μοναδικά κουδούνια.

Αυτό ισχύει και για τα τρία τελευταία κουδούνια.

Τώρα, το όμορφο μαθηματικό κόλπο - για αυτόν τον τρόπο να επιλέξετε τα 5 κουδούνια, ποια είναι η σειρά των 8 κουδουνιών όπου επιλέγουμε ακριβώς αυτά τα 5 κουδούνια; Από την παραπάνω εικόνα, είναι όλες οι παραγγελίες των 5 κουδουνιών ( 5!) και όλες οι σειρές των υπόλοιπων τριών κουδουνιών ( 3!).

Έτσι, για κάθε τρόπο επιλογής 5 κουδουνιών, έχουμε ( 5! * 3!) παραγγελίες 8 κουδουνιών.

Ποιες είναι οι συνολικές πιθανές παραγγελίες των 8 κουδουνιών; 8!.

Θυμηθείτε, για κάθε επιλογή των πρώτων 5 κουδουνιών, έχουμε ( 5! * 3!) παραγγελίες 8 κουδουνιών που δίνουν την ίδια επιλογή.

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

Ways to choose 5 bells * orderings of one choice = Total orderings 

Ετσι,

Ways to choose 5 bells = the total possible orderings / total orderings of one choice. 

Στα μαθηματικά, αυτό γίνεται:

(8 C 5) = 8! / ( 5! * 3!) 

Ας δούμε, έχουμε βρει μια διαισθητική εξήγηση για το πώς να επιλέξουμε 5 πράγματα από τα 8

Τώρα, μπορούμε να το γενικεύσουμε. Εάν έχουμε N πράγματα και θέλουμε να επιλέξουμε R από αυτά, αυτό σημαίνει ότι σχεδιάζουμε μια γραμμή στο R.

Αυτό σημαίνει ότι τα υπόλοιπα αντικείμενα θα είναι N-R. Έτσι, για μία επιλογή Rαντικειμένων, έχουμε R! * (N-R)!παραγγελίες που δίνουν τα ίδια Rαντικείμενα.

Για όλους τους τρόπους επιλογής Rαντικειμένων, έχουμε N! / (R! * (N-R)!)δυνατότητες.

Ο αριθμός των τρόπων επιλογής rαντικειμένων nείναι(n C r) = n! / (r! * (n-r)!)

Σε συνομιλητικούς όρους, το (n C r) προφέρεται επίσης n choose r, το οποίο βοηθά στην ενίσχυση της ιδέας ότι οι συνδυασμοί είναι για την επιλογή αντικειμένων.

Η παραλλαγή - επανεξετάστηκε

Με τον συνδυασμό που έχει γίνει και ξεσκονιστεί, ας επιστρέψουμε στο Μέρος 2 της δουλειάς μας. Ο αγαπητός μας φίλος επέλεξε τα καλύτερα 5 κουδούνια, υπολογίζοντας όλους τους πιθανούς συνδυασμούς των 5 κουδουνιών.

Είναι δική μας δουλειά τώρα να βρούμε την τέλεια μελωδία υπολογίζοντας τον αριθμό των παραγγελιών.

Όμως, αυτό είναι το εύκολο κομμάτι. Γνωρίζουμε ήδη πώς να παραγγείλετε 5 αντικείμενα. Είναι 5!, και τελειώσαμε.

Έτσι, για να παραγάγουμε (παραγγελία) 5 αντικείμενα από τα 8, πρώτα επιλέγουμε 5 στοιχεία και μετά παραγγείλουμε τα 5 στοιχεία

Με άλλα λόγια,

(8 P 5) = (8 C 5) * 5! 

Και αν επεκτείνουμε τον τύπο, (8 P 5) = (8! / ( 5! * 3!)) * 5!

(8 P 5) = 8! / 3!.

Και, έχουμε φτάσει τον πλήρη κύκλο στην αρχική μας φόρμουλα, που προέρχεται σωστά.

Ο αριθμός των τρόπων παραγγελίας rαντικειμένων nείναι(n P r) = n! / (n-r)!

Διαφορά μεταξύ της παραλλαγής και του συνδυασμού

Ελπίζω ότι αυτό κάνει τη διαφορά μεταξύ παραλλαγών και συνδυασμών ξεκάθαρη.

Οι παραλλαγές είναι παραγγελίες, ενώ οι συνδυασμοί είναι επιλογές.

Για να παραγγείλετε στοιχεία N, βρήκαμε δύο διαισθητικούς τρόπους για να καταλάβουμε την απάντηση. Και τα δύο οδηγούν στην απάντηση, N!.

Για να παραμείνετε 5 στα 8 στοιχεία, πρέπει πρώτα να επιλέξετε τα 5 στοιχεία και, στη συνέχεια, να τα παραγγείλετε. Επιλέγετε να χρησιμοποιήσετε και (8 C 5), στη συνέχεια, παραγγείλετε τα 5 χρησιμοποιώντας 5!.

Και η διαίσθηση για την επιλογή Rαπό Nυπολογίζει όλες τις orderings ( N!) και διαιρώντας με orderings όπου η πρώτη Rκαι η τελευταία N-Rπαραμένει το ίδιο ( R!και (N-R)!).

Και, αυτό είναι το μόνο που υπάρχει σε παραλλαγές και συνδυασμούς.

Κάθε προηγμένη παραλλαγή και συνδυασμός το χρησιμοποιεί ως βάση. Συνδυασμός με αντικατάσταση; Ίδια ιδέα. Παραλλαγή με πανομοιότυπα αντικείμενα; Ίδια ιδέα, αλλάζει μόνο ο αριθμός των παραγγελιών, καθώς ορισμένα στοιχεία είναι ίδια.

Αν σας ενδιαφέρει, μπορούμε να αναφερθούμε στις περίπλοκες περιπτώσεις σε ένα άλλο παράδειγμα. Ενημερώστε με στο Twitter.

Δείτε περισσότερες αναρτήσεις στο ιστολόγιό μου και εγγραφείτε στην εβδομαδιαία λίστα αλληλογραφίας.

Σημειώσεις τέλους

  1. Έτσι φαντάζομαι ότι κατάλαβε τα πράγματα. Μην το πάρετε ως μάθημα στην ιστορία.
  2. Οι Ινδοί είχαν, τον 12ο αιώνα, 400 χρόνια πριν.