Αυτό το άρθρο θα επικεντρωθεί σε μια ειδική ενότητα των μαθηματικών που ονομάζεται συνδυαστική. Τύποι, κανόνες, παραδείγματα επίλυσης προβλημάτων - όλα αυτά μπορείτε να τα βρείτε εδώ διαβάζοντας το άρθρο μέχρι το τέλος.
Λοιπόν, τι είναι αυτή η ενότητα; Η Συνδυαστική ασχολείται με το θέμα της μέτρησης οποιωνδήποτε αντικειμένων. Αλλά σε αυτή την περίπτωση, τα αντικείμενα δεν είναι δαμάσκηνα, αχλάδια ή μήλα, αλλά κάτι άλλο. Η συνδυαστική μας βοηθά να βρούμε την πιθανότητα ενός γεγονότος. Για παράδειγμα, όταν παίζετε χαρτιά, ποια είναι η πιθανότητα ο αντίπαλος να έχει ατού; Ή ένα τέτοιο παράδειγμα - ποια είναι η πιθανότητα να πάρετε ακριβώς λευκό από μια σακούλα με είκοσι μπάλες; Είναι για αυτού του είδους τις εργασίες που πρέπει να γνωρίζουμε τουλάχιστον τα βασικά αυτής της ενότητας των μαθηματικών.
Συνδυαστικές διαμορφώσεις
Λαμβάνοντας υπόψη το ζήτημα των βασικών εννοιών και τύπων της συνδυαστικής, δεν μπορούμε παρά να δώσουμε προσοχή στις συνδυαστικές διαμορφώσεις. Χρησιμοποιούνται όχι μόνο για τη σύνθεση, αλλά και για την επίλυση διαφόρων συνδυαστικών προβλημάτων. Παραδείγματα τέτοιων μοντέλων είναι:
- τοποθέτηση;
- μετάθεση;
- συνδυασμός;
- σύνθεση αριθμού;
- διαχωρισμός αριθμού.
Θα μιλήσουμε για τα πρώτα τρία με περισσότερες λεπτομέρειες αργότερα, αλλά θα δώσουμε προσοχή στη σύνθεση και τη διάσπαση σε αυτήν την ενότητα. Όταν μιλούν για τη σύνθεση ενός συγκεκριμένου αριθμού (ας πούμε, α), εννοούν την αναπαράσταση του αριθμού α ως διατεταγμένο άθροισμα ορισμένων θετικών αριθμών. Και ένα μοίρασμα είναι ένα μη διατεταγμένο άθροισμα.
Ενότητες
Πριν πάμε απευθείας στους τύπους της συνδυαστικής και στην εξέταση προβλημάτων, αξίζει να προσέξουμε το γεγονός ότι η συνδυαστική, όπως και άλλες ενότητες των μαθηματικών, έχει τις δικές της υποενότητες. Αυτά περιλαμβάνουν:
- αριθμητικό;
- δομικό;
- extreme;
- θεωρία Ramsey;
- πιθανολογικό;
- τοπολογικό;
- άπειρο.
Στην πρώτη περίπτωση, μιλάμε για αριθμητική συνδυαστική, τα προβλήματα εξετάζουν την απαρίθμηση ή την καταμέτρηση διαφορετικών διαμορφώσεων που σχηματίζονται από στοιχεία συνόλων. Κατά κανόνα, επιβάλλονται ορισμένοι περιορισμοί σε αυτά τα σύνολα (διακρισιμότητα, δυσδιάκριση, δυνατότητα επανάληψης κ.λπ.). Και ο αριθμός αυτών των διαμορφώσεων υπολογίζεται χρησιμοποιώντας τον κανόνα της πρόσθεσης ή του πολλαπλασιασμού, για τον οποίο θα μιλήσουμε λίγο αργότερα. Η δομική συνδυαστική περιλαμβάνει τις θεωρίες των γραφημάτων και των μητροειδών. Ένα παράδειγμα ακραίου προβλήματος συνδυαστικής είναι ποια είναι η μεγαλύτερη διάσταση ενός γραφήματος που ικανοποιεί τις ακόλουθες ιδιότητες… Στην τέταρτη παράγραφο, αναφέραμε τη θεωρία Ramsey, η οποία μελετά την παρουσία κανονικών δομών σε τυχαίες διαμορφώσεις. ΠιθανολογικόΗ συνδυαστική είναι σε θέση να απαντήσει στην ερώτηση - ποια είναι η πιθανότητα ένα δεδομένο σύνολο να έχει μια συγκεκριμένη ιδιότητα. Όπως μπορείτε να μαντέψετε, η τοπολογική συνδυαστική εφαρμόζει μεθόδους στην τοπολογία. Και τέλος, το έβδομο σημείο - η άπειρη συνδυαστική μελετά την εφαρμογή των συνδυαστικών μεθόδων σε άπειρα σύνολα.
Κανόνας προσθήκης
Μεταξύ των τύπων της συνδυαστικής, μπορεί κανείς να βρει αρκετά απλούς, με τους οποίους είμαστε εξοικειωμένοι εδώ και πολύ καιρό. Ένα παράδειγμα είναι ο κανόνας του αθροίσματος. Ας υποθέσουμε ότι μας δίνονται δύο ενέργειες (C και E), εάν είναι αμοιβαία αποκλειόμενες, η ενέργεια C μπορεί να γίνει με διάφορους τρόπους (για παράδειγμα, a) και η ενέργεια E μπορεί να γίνει με β-τρόπους, τότε οποιαδήποτε από αυτές (C ή Ε) μπορεί να γίνει με τρόπους a + b.
Θεωρητικά, αυτό είναι αρκετά δύσκολο να γίνει κατανοητό, θα προσπαθήσουμε να μεταφέρουμε όλη την ουσία με ένα απλό παράδειγμα. Ας πάρουμε τον μέσο αριθμό μαθητών σε μια τάξη - ας πούμε ότι είναι είκοσι πέντε. Ανάμεσά τους δεκαπέντε κορίτσια και δέκα αγόρια. Ένας συνοδός ανατίθεται στην τάξη καθημερινά. Πόσοι τρόποι υπάρχουν για να ορίσετε έναν υπάλληλο της τάξης σήμερα; Η λύση στο πρόβλημα είναι αρκετά απλή, θα καταφύγουμε στον κανόνα της προσθήκης. Το κείμενο της εργασίας δεν λέει ότι μόνο αγόρια ή μόνο κορίτσια μπορούν να είναι σε υπηρεσία. Επομένως, θα μπορούσε να είναι οποιοδήποτε από τα δεκαπέντε κορίτσια ή οποιοδήποτε από τα δέκα αγόρια. Εφαρμόζοντας τον κανόνα του αθροίσματος, παίρνουμε ένα αρκετά απλό παράδειγμα που μπορεί εύκολα να αντιμετωπίσει ένας μαθητής δημοτικού σχολείου: 15 + 10. Έχοντας υπολογίσει, παίρνουμε την απάντηση: είκοσι πέντε. Δηλαδή, υπάρχουν μόνο είκοσι πέντε τρόποιορίστε μια τάξη καθήκοντος για σήμερα.
Κανόνας πολλαπλασιασμού
Ο κανόνας του πολλαπλασιασμού ανήκει επίσης στους βασικούς τύπους των συνδυαστικών. Ας ξεκινήσουμε με τη θεωρία. Ας υποθέσουμε ότι πρέπει να εκτελέσουμε πολλές ενέργειες (α): η πρώτη ενέργεια εκτελείται με 1 τρόπους, η δεύτερη - με 2 τρόπους, η τρίτη - με 3 τρόπους, και ούτω καθεξής έως ότου η τελευταία ενέργεια α-ενέργεια εκτελεστεί με τρόπους sa. Τότε όλες αυτές οι ενέργειες (από τις οποίες έχουμε ένα σύνολο) μπορούν να εκτελεστούν με Ν τρόπους. Πώς να υπολογίσετε το άγνωστο N; Ο τύπος θα μας βοηθήσει σε αυτό: N \u003d c1c2c3…ca.
Και πάλι, τίποτα δεν είναι ξεκάθαρο στη θεωρία, ας προχωρήσουμε σε ένα απλό παράδειγμα εφαρμογής του κανόνα του πολλαπλασιασμού. Ας πάρουμε την ίδια τάξη των είκοσι πέντε ατόμων, στην οποία σπουδάζουν δεκαπέντε κορίτσια και δέκα αγόρια. Μόνο που αυτή τη φορά χρειάζεται να διαλέξουμε δύο συνοδούς. Μπορούν να είναι είτε μόνο αγόρια είτε κορίτσια, είτε αγόρι με κορίτσι. Στρέφουμε στη στοιχειώδη λύση του προβλήματος. Επιλέγουμε τον πρώτο συνοδό, όπως αποφασίσαμε στην τελευταία παράγραφο, έχουμε είκοσι πέντε πιθανές επιλογές. Το δεύτερο άτομο σε υπηρεσία μπορεί να είναι οποιοδήποτε από τα υπόλοιπα άτομα. Είχαμε είκοσι πέντε μαθητές, επιλέξαμε έναν, που σημαίνει ότι όποιος από τους υπόλοιπους είκοσι τέσσερα άτομα μπορεί να είναι ο δεύτερος στην υπηρεσία. Τέλος, εφαρμόζουμε τον κανόνα του πολλαπλασιασμού και βρίσκουμε ότι οι δύο συνοδοί μπορούν να επιλεγούν με εξακόσιους τρόπους. Πήραμε αυτόν τον αριθμό πολλαπλασιάζοντας το είκοσι πέντε και το είκοσι τέσσερα.
Ανταλλαγή
Τώρα θα εξετάσουμε έναν ακόμη συνδυαστικό τύπο. Σε αυτή την ενότητα του άρθρου, εμείςΑς μιλήσουμε για μεταθέσεις. Εξετάστε αμέσως το πρόβλημα με ένα παράδειγμα. Ας πάρουμε μπάλες του μπιλιάρδου, έχουμε τον ν-ο αριθμό από αυτές. Πρέπει να υπολογίσουμε: πόσες επιλογές υπάρχουν για να τις τακτοποιήσουμε στη σειρά, δηλαδή να φτιάξουμε ένα διατεταγμένο σετ.
Ας ξεκινήσουμε, αν δεν έχουμε μπάλες, τότε έχουμε και μηδενικές επιλογές τοποθέτησης. Και αν έχουμε μία μπάλα, τότε η διάταξη είναι επίσης η ίδια (μαθηματικά, αυτό μπορεί να γραφτεί ως εξής: Р1=1). Δύο μπάλες μπορούν να ταξινομηθούν με δύο διαφορετικούς τρόπους: 1, 2 και 2, 1. Επομένως, Р2=2. Τρεις μπάλες μπορούν να ταξινομηθούν με έξι τρόπους (Р3=6): 1, 2, 3; 1, 3, 2; 2, 1, 3; 2, 3, 1; 3, 2, 1; 3, 1, 2. Και αν δεν υπάρχουν τρεις τέτοιες μπάλες, αλλά δέκα ή δεκαπέντε; Το να απαριθμήσουμε όλες τις πιθανές επιλογές είναι πολύ μεγάλο, τότε η συνδυαστική έρχεται να μας βοηθήσει. Ο τύπος μετάθεσης θα μας βοηθήσει να βρούμε την απάντηση στην ερώτησή μας. Pn=nP(n-1). Αν προσπαθήσουμε να απλοποιήσουμε τον τύπο, παίρνουμε: Pn=n (n - 1) … 21. Και αυτό είναι το γινόμενο των πρώτων φυσικών αριθμών. Ένας τέτοιος αριθμός ονομάζεται παραγοντικός και συμβολίζεται ως n!
Ας εξετάσουμε το πρόβλημα. Ο αρχηγός κάθε πρωί χτίζει το απόσπασμά του σε μια σειρά (είκοσι άτομα). Υπάρχουν τρεις καλύτεροι φίλοι στο απόσπασμα - Kostya, Sasha και Lesha. Ποια είναι η πιθανότητα να είναι ο ένας δίπλα στον άλλο; Για να βρείτε την απάντηση στην ερώτηση, πρέπει να διαιρέσετε την πιθανότητα ενός «καλού» αποτελέσματος με τον συνολικό αριθμό των αποτελεσμάτων. Ο συνολικός αριθμός μεταθέσεων είναι 20!=2,5 εκατομμύριο. Πώς να μετρήσετε τον αριθμό των "καλών" αποτελεσμάτων; Ας υποθέσουμε ότι ο Kostya, η Sasha και η Lesha είναι ένας υπεράνθρωπος. Μετά εμείςΈχουμε μόνο δεκαοκτώ θέματα. Ο αριθμός των μεταθέσεων σε αυτή την περίπτωση είναι 18=6,5 τετρασεκατομμύρια. Με όλα αυτά, ο Kostya, η Sasha και η Lesha μπορούν αυθαίρετα να κινηθούν μεταξύ τους στο αδιαίρετο τρίποντό τους, και αυτό είναι ακόμη 3!=6 επιλογές. Έχουμε λοιπόν 18 «καλούς» αστερισμούς συνολικά!3! Απλά πρέπει να βρούμε την επιθυμητή πιθανότητα: (18!3!) / 20! Το οποίο είναι περίπου 0,016. Εάν μετατραπεί σε ποσοστό, αποδεικνύεται ότι είναι μόνο 1,6%.
Διαμονή
Τώρα θα εξετάσουμε έναν άλλο πολύ σημαντικό και απαραίτητο συνδυαστικό τύπο. Η διαμονή είναι το επόμενο θέμα μας, το οποίο σας προτείνουμε να εξετάσετε σε αυτήν την ενότητα του άρθρου. Θα γίνουμε πιο περίπλοκοι. Ας υποθέσουμε ότι θέλουμε να εξετάσουμε πιθανές μεταθέσεις, μόνο όχι από ολόκληρο το σύνολο (n), αλλά από ένα μικρότερο (m). Δηλαδή, θεωρούμε μεταθέσεις n στοιχείων κατά m.
Οι βασικοί τύποι της συνδυαστικής δεν πρέπει απλώς να απομνημονεύονται, αλλά να κατανοούνται. Ακόμη και παρά το γεγονός ότι γίνονται πιο περίπλοκα, αφού δεν έχουμε μία παράμετρο, αλλά δύο. Ας υποθέσουμε ότι m \u003d 1, μετά A \u003d 1, m \u003d 2, μετά A \u003d n(n - 1). Εάν απλοποιήσουμε περαιτέρω τον τύπο και μεταβούμε στη σημειογραφία χρησιμοποιώντας παραγοντικά, θα έχουμε έναν αρκετά συνοπτικό τύπο: A \u003d n! / (n - m)!
Συνδυασμός
Έχουμε εξετάσει σχεδόν όλους τους βασικούς τύπους συνδυαστικής με παραδείγματα. Τώρα ας περάσουμε στο τελικό στάδιο της εξέτασης του βασικού μαθήματος της συνδυαστικής - να γνωρίσουμε τον συνδυασμό. Τώρα θα επιλέξουμε m στοιχεία από το n που έχουμε, ενώ θα τα επιλέξουμε όλα με όλους τους δυνατούς τρόπους. Σε τι διαφέρει λοιπόν αυτό από τη διαμονή; Εμείς δεν θαεξετάστε την τάξη. Αυτό το μη ταξινομημένο σετ θα είναι ένας συνδυασμός.
Εισαγάγετε αμέσως τον συμβολισμό: Γ. Παίρνουμε τοποθετήσεις m μπάλες από n. Σταματάμε να προσέχουμε την τάξη και παίρνουμε επαναλαμβανόμενους συνδυασμούς. Για να πάρουμε τον αριθμό των συνδυασμών, πρέπει να διαιρέσουμε τον αριθμό των τοποθετήσεων με m! (m παραγοντικό). Δηλαδή, C \u003d A / m! Έτσι, υπάρχουν μερικοί τρόποι για να επιλέξετε από n μπάλες, περίπου ίσες με πόσες να επιλέξετε σχεδόν τα πάντα. Υπάρχει μια λογική έκφραση για αυτό: το να επιλέγεις λίγο είναι το ίδιο με το να πετάς σχεδόν τα πάντα. Είναι επίσης σημαντικό να αναφέρουμε σε αυτό το σημείο ότι ο μέγιστος αριθμός συνδυασμών μπορεί να επιτευχθεί όταν προσπαθείτε να επιλέξετε τα μισά από τα στοιχεία.
Πώς να επιλέξετε έναν τύπο για να λύσετε ένα πρόβλημα;
Έχουμε εξετάσει λεπτομερώς τους βασικούς τύπους της συνδυαστικής: τοποθέτηση, μετάθεση και συνδυασμός. Τώρα το καθήκον μας είναι να διευκολύνουμε την επιλογή της απαραίτητης φόρμουλας για την επίλυση του προβλήματος στη συνδυαστική. Μπορείτε να χρησιμοποιήσετε το ακόλουθο σχετικά απλό σχήμα:
- Ρωτήστε τον εαυτό σας: λαμβάνεται υπόψη η σειρά των στοιχείων στο κείμενο του προβλήματος;
- Αν η απάντηση είναι όχι, χρησιμοποιήστε τον τύπο συνδυασμού (C=n! / (m!(n - m)!)).
- Εάν η απάντηση είναι όχι, τότε πρέπει να απαντήσετε σε μία ακόμη ερώτηση: περιλαμβάνονται όλα τα στοιχεία στον συνδυασμό;
- Αν η απάντηση είναι ναι, χρησιμοποιήστε τον τύπο μετάθεσης (P=n!).
- Αν η απάντηση είναι όχι, χρησιμοποιήστε τον τύπο κατανομής (A=n! / (n - m)!).
Παράδειγμα
Έχουμε εξετάσει τα στοιχεία της συνδυαστικής, τους τύπους και ορισμένα άλλα ζητήματα. Τώρα ας προχωρήσουμε στοεξετάζοντας ένα πραγματικό πρόβλημα. Φανταστείτε ότι έχετε ένα ακτινίδιο, ένα πορτοκάλι και μια μπανάνα μπροστά σας.
Ερώτηση ένα: με πόσους τρόπους μπορούν να αναδιαταχθούν; Για να γίνει αυτό, χρησιμοποιούμε τον τύπο μετάθεσης: P=3!=6 τρόποι.
Ερώτηση δεύτερη: με πόσους τρόπους μπορεί να επιλεγεί ένα φρούτο; Αυτό είναι προφανές, έχουμε μόνο τρεις επιλογές - επιλέξτε ακτινίδιο, πορτοκάλι ή μπανάνα, αλλά εφαρμόζουμε τον τύπο συνδυασμού: C \u003d 3! / (2!1!)=3.
Ερώτηση τρίτη: με πόσους τρόπους μπορούν να επιλεγούν δύο φρούτα; Τι επιλογές έχουμε; Ακτινίδιο και πορτοκάλι? Ακτινίδιο και μπανάνα? πορτοκάλι και μπανάνα. Δηλαδή, τρεις επιλογές, αλλά αυτό είναι εύκολο να το ελέγξετε χρησιμοποιώντας τον τύπο συνδυασμού: C \u003d 3! / (1!2!)=3
Ερώτηση τέταρτη: με πόσους τρόπους μπορούν να επιλεγούν τρία φρούτα; Όπως μπορείτε να δείτε, υπάρχει μόνο ένας τρόπος για να επιλέξετε τρία φρούτα: πάρτε ένα ακτινίδιο, ένα πορτοκάλι και μια μπανάνα. C=3! / (0!3!)=1.
Ερώτηση πέμπτη: με πόσους τρόπους μπορείτε να επιλέξετε τουλάχιστον ένα φρούτο; Αυτή η συνθήκη υποδηλώνει ότι μπορούμε να πάρουμε ένα, δύο ή και τα τρία φρούτα. Επομένως, προσθέτουμε C1 + C2 + C3=3 + 3 + 1=7. Δηλαδή, έχουμε επτά τρόπους να πάρουμε τουλάχιστον ένα φρούτο από το τραπέζι.
