KOMBINATORIK
Die Kombinatorik ist ein Zweig der Mathematik, der sich mit den Problemen der Auswahl und Anordnung von Elementen aus einer bestimmten Grundmenge nach vorgegebenen Regeln befasst. Formeln und Prinzipien der Kombinatorik werden in der Wahrscheinlichkeitstheorie verwendet, um die Wahrscheinlichkeit zufälliger Ereignisse zu berechnen und dementsprechend Verteilungsgesetze zu erhalten zufällige Variablen. Dies wiederum ermöglicht es uns, die Muster von Massenzufallsphänomenen zu untersuchen, was für ein korrektes Verständnis der statistischen Muster, die sich in Natur und Technologie manifestieren, sehr wichtig ist.
Regeln für Addition und Multiplikation in der Kombinatorik
Summenregel. Wenn sich zwei Aktionen A und B gegenseitig ausschließen und Aktion A auf m Arten und B auf n Arten ausgeführt werden kann, dann kann eine dieser Aktionen (entweder A oder B) auf n + m Arten ausgeführt werden.
Beispiel 1.
In der Klasse sind 16 Jungen und 10 Mädchen. Auf wie viele Arten kann ein Dienstoffizier eingesetzt werden?
Lösung
Es kann entweder ein Junge oder ein Mädchen zum Dienst eingesetzt werden, d.h. Der diensthabende Beamte kann einer der 16 Jungen oder einer der 10 Mädchen sein.
Mithilfe der Summenregel stellen wir fest, dass ein Dienstoffizier auf 16+10=26 Arten eingesetzt werden kann.
Produktregel. Es seien k Aktionen erforderlich, die nacheinander ausgeführt werden müssten. Wenn die erste Aktion auf n 1 Arten ausgeführt werden kann, die zweite Aktion auf n 2 Arten, die dritte auf n 3 Arten usw. bis zur k-ten Aktion, die auf n k Arten ausgeführt werden kann, können alle k Aktionen zusammen ausgeführt werden :
Wege.
Beispiel 2.
In der Klasse sind 16 Jungen und 10 Mädchen. Auf wie viele Arten können zwei Dienstoffiziere ernannt werden?
Lösung
Zum ersten Diensthabenden kann entweder ein Junge oder ein Mädchen ernannt werden. Weil In der Klasse sind 16 Jungen und 10 Mädchen, dann kann man den ersten Diensthabenden auf 16+10=26 Arten ernennen.
Nachdem wir den ersten diensthabenden Offizier ausgewählt haben, können wir aus den verbleibenden 25 Personen den zweiten auswählen, d. h. 25 Wege.
Nach dem Multiplikationssatz können zwei Begleiter auf 26*25=650 Arten ausgewählt werden.
Kombinationen ohne Wiederholung. Kombinationen mit Wiederholungen
Ein klassisches Problem der Kombinatorik ist das Problem der Anzahl der Kombinationen ohne Wiederholungen, dessen Inhalt durch die Frage ausgedrückt werden kann: wie viele Wege Kann wählen komme aus n verschiedene Artikel?
Beispiel 3.
Sie müssen 4 von 10 verschiedenen Büchern auswählen, die Sie verschenken können. Auf wie viele Arten kann dies geschehen?
Lösung
Wir müssen 4 von 10 Büchern auswählen, wobei die Reihenfolge der Auswahl keine Rolle spielt. Daher müssen Sie die Anzahl der Kombinationen von 10 Elementen von 4 ermitteln:
.
Betrachten Sie das Problem der Anzahl der Kombinationen mit Wiederholungen: Es gibt r identische Objekte von jedem der n verschiedenen Typen; wie viele Wege Kann wählen komme aus diese (n*r) Artikel?
.
Beispiel 4.
Die Konditorei verkaufte 4 Kuchensorten: Napoleons, Eclairs, Shortbread und Blätterteig. Auf wie viele Arten kann man 7 Kuchen kaufen?
Lösung
Weil Unter 7 Kuchen dürfen Kuchen der gleichen Sorte sein, dann wird die Anzahl der Möglichkeiten, 7 Kuchen zu kaufen, durch die Anzahl der Kombinationen mit Wiederholungen von 7 bis 4 bestimmt.
.
Platzierungen ohne Wiederholung. Platzierungen mit Wiederholungen
Ein klassisches Problem der Kombinatorik ist das Problem der Anzahl der Platzierungen ohne Wiederholungen, dessen Inhalt durch die Frage ausgedrückt werden kann: wie viele Wege Kann wählen Und Post Von Ich bin anders setzt komme aus n anders Artikel?
Beispiel 5.
Manche Zeitungen haben 12 Seiten. Auf den Seiten dieser Zeitung müssen vier Fotos platziert werden. Auf wie viele Arten kann dies geschehen, wenn keine Seite der Zeitung mehr als ein Foto enthalten soll?
Lösung.
Bei dieser Aufgabe wählen wir nicht nur Fotos aus, sondern platzieren sie auf bestimmten Seiten der Zeitung, und jede Seite der Zeitung sollte nicht mehr als ein Foto enthalten. Somit reduziert sich das Problem auf das klassische Problem der Bestimmung der Anzahl der Platzierungen ohne Wiederholungen von 12 Elementen von 4 Elementen:
Somit können 4 Fotos auf 12 Seiten auf 11.880 Arten angeordnet werden.
Ein klassisches Problem der Kombinatorik ist auch das Problem der Anzahl der Platzierungen mit Wiederholungen, dessen Inhalt durch die Frage ausgedrückt werden kann: wie viele Wege Kann DuBArmee Und Post Von Ich bin anders setzt komme aus n Artikel,Mitbereit welche Es gibt das gleiche?
Beispiel 6.
Aus seinem Brettspielset hatte der Junge noch Stempel mit den Nummern 1, 3 und 7. Er beschloss, mit diesen Stempeln alle Bücher mit fünfstelligen Nummern zu versehen, um einen Katalog zu erstellen. Wie viele verschiedene fünfstellige Zahlen kann ein Junge erschaffen?
Permutationen ohne Wiederholung. Permutationen mit Wiederholungen
Ein klassisches Problem der Kombinatorik ist das Problem der Anzahl der Permutationen ohne Wiederholung, dessen Inhalt durch die Frage ausgedrückt werden kann: wie viele Wege Kann Post N verschieden Artikel An n anders setzt?
Beispiel 7.
Wie viele vierbuchstabige „Wörter“ können Sie aus den Buchstaben des Wortes „Ehe“ bilden?
Lösung
Die allgemeine Bevölkerung besteht aus den 4 Buchstaben des Wortes „Ehe“ (b, p, a, k). Die Anzahl der „Wörter“ wird durch die Permutationen dieser 4 Buchstaben bestimmt, d. h.
Für den Fall, dass es unter den ausgewählten n Elementen identische gibt (Auswahl mit Rückgabe), kann das Problem der Anzahl der Permutationen mit Wiederholungen durch die Frage ausgedrückt werden: Auf wie viele Arten können n Objekte, die sich an n verschiedenen Orten befinden, neu angeordnet werden, wenn es unter n Objekten k verschiedene Typen gibt (k< n), т. е. есть одинаковые предметы.
Beispiel 8.
Wie viele verschiedene Buchstabenkombinationen lassen sich aus den Buchstaben des Wortes „Mississippi“ bilden?
Lösung
Es gibt 1 Buchstaben „m“, 4 Buchstaben „i“, 3 Buchstaben „c“ und 1 Buchstaben „p“, also insgesamt 9 Buchstaben. Daher ist die Anzahl der Permutationen mit Wiederholungen gleich
HINTERGRUNDZUSAMMENFASSUNG ZUM ABSCHNITT „KOMBINATORIK“
Alle N Elemente und keines werden wiederholt, dann handelt es sich um ein Problem bezüglich der Anzahl der Permutationen. Die Lösung kann einfach gefunden werden. Der erste Platz in einer Reihe kann jedes von N Elementen sein, daher gibt es N Optionen. An zweiter Stelle stehen alle, mit Ausnahme derjenigen, die bereits für den ersten Platz verwendet wurden. Daher gibt es für jede der N Optionen, die bereits gefunden wurden, (N – 1) zweitplatzierte Optionen, und die Gesamtzahl der Kombinationen beträgt N*(N – 1).
Dasselbe kann für die übrigen Elemente der Serie wiederholt werden. Für den allerletzten Platz bleibt nur noch eine Option – das letzte verbleibende Element. Für den vorletzten gibt es zwei Möglichkeiten und so weiter.
Daher sind für eine Reihe von N sich nicht wiederholenden Elementen die möglichen Permutationen gleich dem Produkt aller ganzen Zahlen von 1 bis N. Dieses Produkt wird Fakultät von N genannt und mit N! bezeichnet! (lesen Sie „en faktorial“).
Im vorherigen Fall stimmten die Anzahl der möglichen Elemente und die Anzahl der Stellen in der Zeile überein und ihre Anzahl war gleich N. Es ist jedoch eine Situation möglich, in der es weniger Stellen in der Zeile gibt als mögliche Elemente. Mit anderen Worten, die Anzahl der Elemente in der Stichprobe entspricht einer bestimmten Zahl M und M< N. В этом случае задача определения количества возможных комбинаций может иметь два различных варианта.
Zuerst müssen Sie möglicherweise die Gesamtzahl zählen mögliche Wege, die verwendet werden kann, um M Elemente aus N in einer Reihe anzuordnen. Solche Methoden werden Platzierungen genannt.
Zweitens könnte der Forscher daran interessiert sein, auf wie viele Arten M Elemente aus N ausgewählt werden können. In diesem Fall ist die Reihenfolge der Elemente nicht mehr wichtig, aber zwei beliebige Optionen müssen sich um mindestens ein Element voneinander unterscheiden . Solche Methoden werden Kombinationen genannt.
Um die Anzahl der Platzierungen von M Elementen aus N zu ermitteln, können Sie auf die gleiche Argumentationsmethode wie bei Permutationen zurückgreifen. An erster Stelle kann es immer noch N Elemente geben, an zweiter Stelle N - 1 und so weiter. Für den letzten Platz ist die Anzahl der möglichen Optionen jedoch nicht gleich eins, sondern (N – M + 1), da nach Abschluss der Platzierung noch (N – M) ungenutzte Elemente vorhanden sind.
Somit ist die Anzahl der Platzierungen von M Elementen aus N gleich dem Produkt aller ganzen Zahlen von (N - M + 1) bis N, oder, was dasselbe ist, dem Quotienten N!/(N - M)!.
Offensichtlich wird die Anzahl der Kombinationen von M Elementen aus N geringer sein als die Anzahl der Platzierungen. Für jede mögliche Kombination gibt es ein M! Mögliche Platzierungen abhängig von der Reihenfolge der Elemente dieser Kombination. Um diese Menge zu ermitteln, müssen Sie daher die Anzahl der Platzierungen von M Elementen aus N durch N! dividieren. Mit anderen Worten, die Anzahl der Kombinationen von M Elementen aus N ist gleich N!/(M!*(N - M)!).
Freunde! Da ich dieses tote Notizbuch bereits habe, werde ich es nutzen, um Ihnen ein Problem zu stellen, mit dem sich gestern drei Physiker, zwei Wirtschaftswissenschaftler, einer vom Polytechnikum und einer von den Geisteswissenschaften beschäftigt haben. Wir haben unser ganzes Gehirn kaputt gemacht und kommen ständig zu unterschiedlichen Ergebnissen. Vielleicht gibt es unter euch Programmierer und Mathematikgenies, außerdem ist das Problem meist ein Schulproblem und sehr einfach, wir können die Formel einfach nicht herleiten. Weil wir ausgestiegen sind exakte Wissenschaften und stattdessen schreiben wir aus irgendeinem Grund Bücher und zeichnen Bilder. Entschuldigung.
Also der Hintergrund.
Ich bekam eine neue Bankkarte und wie üblich erriet ich spielerisch deren PIN-Code. Aber nicht hintereinander. Ich meine, sagen wir mal, der PIN-Code wäre 8794, und ich habe 9748 gesagt. Das heißt, ich triumphiere habe alle Zahlen erraten, die in dieser vierstelligen Zahl enthalten waren. Nun ja, nicht die Zahl selbst, aber eben seine Bestandteile Ich habe mich gefragt. Aber die Zahlen stimmen alle! HINWEIS – Ich habe nach dem Zufallsprinzip gehandelt, das heißt, ich musste die bereits bekannten Zahlen nicht in der richtigen Reihenfolge anordnen, ich habe einfach im Geiste gehandelt: Hier gibt es vier Zahlen, die mir unbekannt sind, und ich glaube, dass es unter ihnen welche geben könnte 9, 7, 4 und 8, und ihre Reihenfolge ist nicht wichtig. Wir haben uns sofort gefragt, Wie viele Möglichkeiten hatte ich?(wahrscheinlich um zu verstehen, wie cool es ist, dass ich es einfach genommen und geraten habe). Das heißt, aus wie vielen Kombinationen von vier Zahlen musste ich wählen? Und dann brach natürlich die Hölle los. Den ganzen Abend über explodierten unsere Köpfe, und am Ende kamen wir alle absolut raus verschiedene Varianten Antwort! Ich fing sogar an, alle diese Kombinationen hintereinander in ein Notizbuch zu schreiben, als sie zunahmen, aber bei vierhundert wurde mir klar, dass es mehr als vierhundert waren (auf jeden Fall widerlegte dies die Antwort des Physikers Thrash, der mir das versicherte waren vierhundert Kombinationen, aber das ist immer noch nicht ganz klar) - und gaben auf.
Eigentlich, Kern der Frage. Wie groß ist die Wahrscheinlichkeit, vier in einer vierstelligen Zahl enthaltene Zahlen (in beliebiger Reihenfolge) zu erraten?
Oder auch nicht, formulieren wir es um (ich bin Humanist, verzeihen Sie mir, obwohl ich schon immer eine große Schwäche für Mathematik hatte), um es klarer und präziser zu machen. Wie viele nicht repetitiv Zahlenkombinationen, die in der Reihe der Ordnungszahlen von 0 bis 9999 enthalten sind? ( Bitte verwechseln Sie dies nicht mit der Frage „Wie viele Kombinationen?“ nicht repetitiv Zahlen“!!! Nummern dürfen wiederholt werden! Ich meine, 2233 und 3322 sind in diesem Fall die gleiche Kombination!!).
Oder noch konkreter. Ich muss viermal eine von zehn Zahlen erraten. Aber nicht hintereinander.
Na ja, oder etwas anderes. Generell muss ich herausfinden, wie viele Möglichkeiten ich für die Zahlenkombination hatte, aus der der Karten-PIN-Code besteht. Hilfe, gute Leute! Wenn Sie helfen, schreiben Sie bitte nicht sofort, dass es dafür 9999 Optionen gibt(Das kam gestern allen als erstes in den Sinn), denn das ist Unsinn – schließlich sind es aus der Perspektive, die uns beunruhigt, die Zahl 1234, die Zahl 3421, die Zahl 4312 und so weiter das gleiche! Nun ja, die Nummern können wiederholt werden, denn es gibt einen PIN-Code 1111 oder zum Beispiel 0007. Anstelle eines PIN-Codes kann man sich auch eine Autonummer vorstellen. Nehmen wir an, wie groß ist die Wahrscheinlichkeit, alle einstelligen Zahlen zu erraten, aus denen die Autonummer besteht? Oder um ganz auf die Wahrscheinlichkeitstheorie zu verzichten: Aus wie vielen Zahlenkombinationen musste ich eine auswählen?
Bitte untermauern Sie Ihre Antworten und Argumente mit einigen präzisen Formeln, denn gestern sind wir fast verrückt geworden. Vielen Dank euch allen im Voraus!
P.S. Eins schlauer Mann, ein Programmierer, Künstler und Erfinder, schlug einfach sehr korrekt die richtige Lösung für das Problem vor und bescherte mir damit ein paar Minuten gute Laune: „ Die Lösung des Problems ist folgende: Sie hat eine Zwangsstörung, die Behandlung lautet: heiraten und Tomaten anbauen. Wenn ich sie wäre, würde mich nicht die Frage „Wie hoch ist die Wahrscheinlichkeit“ mehr beschäftigen, sondern die Frage „Warum achte ich auf all diese Zahlen?“? Im Allgemeinen gibt es nicht einmal etwas hinzuzufügen :)
Der folgende Rechner ist so konzipiert, dass er alle Kombinationen von n mal m Elementen generiert.
Die Anzahl solcher Kombinationen kann mit dem Elements of Combinatorics-Rechner berechnet werden. Permutationen, Platzierungen, Kombinationen.
Beschreibung des Generierungsalgorithmus unter dem Rechner.
Algorithmus
Kombinationen werden in lexikografischer Reihenfolge generiert. Der Algorithmus arbeitet mit Ordinalindizes von Mengenelementen.
Schauen wir uns den Algorithmus anhand eines Beispiels an.
Betrachten Sie zur Vereinfachung der Darstellung eine Menge von fünf Elementen, deren Indizes mit 1 beginnen, nämlich 1 2 3 4 5.
Es ist erforderlich, alle Kombinationen der Größe m = 3 zu generieren.
Die erste Kombination der angegebenen Größe m wird zuerst initialisiert – Indizes in aufsteigender Reihenfolge
1 2 3
Als nächstes wird das letzte Element überprüft, d. h. i = 3. Wenn sein Wert kleiner als n - m + i ist, wird er um 1 erhöht.
1 2 4
Das letzte Element wird erneut überprüft und erneut inkrementiert.
1 2 5
Nun ist der Wert des Elements gleich dem maximal möglichen: n - m + i = 5 - 3 + 3 = 5, das vorherige Element mit i = 2 wird überprüft.
Wenn sein Wert kleiner als n - m + i ist, wird er um 1 erhöht und für alle darauf folgenden Elemente ist der Wert gleich dem Wert des vorherigen Elements plus 1.
1 (2+1)3 (3+1)4 = 1 3 4
Als nächstes prüfen wir erneut, ob i = 3 ist.
1 3 5
Überprüfen Sie dann, ob i = 2 ist.
1 4 5
Dann kommt i = 1 an die Reihe.
(1+1)2 (2+1)3 (3+1)4 = 2 3 4
Und weiter,
2 3 5
2 4 5
3 4 5
- die letzte Kombination, da alle ihre Elemente gleich n - m + i sind.
Trotz der wichtigen Rolle von PIN-Codes in der weltweiten Infrastruktur gibt es keine wissenschaftliche Forschung darüber, wie Menschen PIN-Codes tatsächlich wählen.
Die Forscher der Universität Cambridge, Sören Preibusch und Ross Anderson, korrigierten die Situation, indem sie die Weltneuheit veröffentlichten quantitative Analyse Schwierigkeiten beim Erraten des 4-stelligen Bank-PIN-Codes.
Anhand von Daten zu Passwortlecks aus Nicht-Banken-Quellen und Online-Umfragen haben Wissenschaftler herausgefunden, dass Benutzer die Wahl von PIN-Codes viel ernster nehmen als die Wahl von Passwörtern für Websites: Die meisten Codes enthalten eine nahezu zufällige Reihe von Zahlen. Allerdings finden sich unter den Ausgangsdaten auch einfache Kombinationen und Geburtstage – das heißt, mit etwas Glück kann ein Angreifer den begehrten Code einfach erraten.
Ausgangspunkt der Studie war ein Satz vierstelliger Passwortsequenzen aus der RockYou-Datenbank (1,7 Millionen) und eine Datenbank mit 200.000 PIN-Codes aus dem iPhone-Bildschirmsperrprogramm (die Datenbank wurde vom Anwendungsentwickler Daniel Amitay bereitgestellt). . In den aus diesen Daten erstellten Diagrammen tauchen interessante Muster auf – Datumsangaben, Jahre, sich wiederholende Zahlen und sogar PIN-Codes, die auf 69 enden. Basierend auf diesen Beobachtungen erstellten Wissenschaftler ein lineares Regressionsmodell, das die Beliebtheit jedes PIN-Codes in Abhängigkeit von 25 Faktoren schätzt B. ob es sich bei dem Code um ein DDMM-Datum handelt, ob es sich um eine aufsteigende Reihenfolge handelt usw. Das Allgemeine Bedingungen entsprechen 79 % bzw. 93 % der PIN-Codes in jedem der Sätze.
Daher wählen Benutzer 4-stellige Codes basierend auf nur wenigen einfachen Faktoren. Wenn Bank-PIN-Codes auf diese Weise gewählt würden, könnten 8-9 % davon in nur drei Versuchen erraten werden! Aber natürlich achten die Leute viel mehr auf Bankleitzahlen. Da kein großer Satz realer Bankdaten zur Verfügung stand, befragten die Forscher mehr als 1.300 Personen, um festzustellen, wie sehr sich echte PIN-Codes von den bereits berücksichtigten unterschieden. Angesichts der Besonderheiten der Studie wurden die Befragten nicht nach den Codes selbst gefragt, sondern nur nach deren Einhaltung eines der oben genannten Faktoren (Erhöhung, DDMM-Format usw.).
Es stellte sich heraus, dass die Leute ihre Bank-PIN-Codes tatsächlich viel sorgfältiger wählen. Etwa ein Viertel der Befragten nutzt eine von der Bank zufällig generierte PIN. Mehr als ein Drittel wählt seine PIN anhand einer alten Telefonnummer, einer Studentenausweisnummer oder einer anderen zufällig erscheinenden Zahlenfolge. Den Ergebnissen zufolge verwenden 64 % der Karteninhaber eine pseudozufällige PIN, was viel mehr ist als die 23–27 % in früheren Experimenten mit Nicht-Bankcodes. Weitere 5 % verwenden ein digitales Muster (z. B. 4545) und 9 % bevorzugen ein Tastaturmuster (z. B. 2684). Im Allgemeinen hat ein Angreifer bei sechs Versuchen (drei mit einem Geldautomaten und drei mit einem Zahlungsterminal) eine Chance von weniger als 2 %, den PIN-Code der Karte einer anderen Person zu erraten.
| Faktor | Beispiel | RockYou | iPhone | Umfrage |
|---|---|---|---|---|
| Termine | ||||
| TTMM | 2311 | 5.26 | 1.38 | 3.07 |
| DMGG | 3876 | 9.26 | 6.46 | 5.54 |
| MMDD | 1123 | 10.00 | 9.35 | 3.66 |
| MMJJ | 0683 | 0.67 | 0.20 | 0.94 |
| JJJJ | 1984 | 33.39 | 7.12 | 4.95 |
| Gesamt | 58.57 | 24.51 | 22.76 | |
| Tastaturmuster | ||||
| benachbart | 6351 | 1.52 | 4.99 | - |
| Quadrat | 1425 | 0.01 | 0.58 | - |
| Winkel | 9713 | 0.19 | 1.06 | - |
| kreuzen | 8246 | 0.17 | 0.88 | - |
| diagonale Linie | 1590 | 0.10 | 1.36 | - |
| horizontale Linie | 5987 | 0.34 | 1.42 | - |
| Wort | 5683 | 0.70 | 8.39 | - |
| vertikale Linie | 8520 | 0.06 | 4.28 | - |
| Gesamt | 3.09 | 22.97 | 8.96 | |
| Digitales Muster | ||||
| endet mit 69 | 6869 | 0.35 | 0.57 | - |
| nur Zahlen 0-3 | 2000 | 3.49 | 2.72 | - |
| nur Zahlen 0-6 | 5155 | 4.66 | 5.96 | - |
| sich wiederholende Paare | 2525 | 2.31 | 4.11 | - |
| gleiche Zahlen | 6666 | 0.40 | 6.67 | - |
| absteigende Reihenfolge | 3210 | 0.13 | 0.29 | - |
| zunehmende Reihenfolge | 4567 | 3.83 | 4.52 | - |
| Gesamt | 15.16 | 24.85 | 4.60 | |
| Zufälliges Wählen von Nummern | 23.17 | 27.67 | 63.68 | |
Alles wäre in Ordnung, aber leider wählt ein erheblicher Teil der Befragten (23 %) einen PIN-Code in Form eines Datums – und fast ein Drittel von ihnen verwendet ihr Geburtsdatum. Das ändert sich deutlich, denn fast alle (99 %) der Befragten antworteten, dass sie neben Bankkarten auch diverse Ausweisdokumente mit diesem aufgedruckten Datum im Portemonnaie aufbewahren. Kennt ein Angreifer den Geburtstag des Karteninhabers, steigt die Wahrscheinlichkeit, den PIN-Code zu erraten, bei kompetenter Vorgehensweise auf 9 %.
100 beliebtesten PIN-Codes
0000, 0101-0103, 0110, 0111, 0123, 0202, 0303, 0404, 0505, 0606, 0707, 0808, 0909, 1010, 1101-1103, 1110-1112, 1123, 1201-1203, 1210-1212, 1234, 1956-2015, 2222, 2229, 2580, 3333, 4444, 5252, 5683, 6666, 7465, 7667.
P.S. In der Praxis ist es für einen Angreifer natürlich viel einfacher, Ihren PIN-Code auszuspionieren, als ihn zu erraten. Aber Sie können sich auch in einer scheinbar aussichtslosen Situation vor dem Spähen schützen:
Kombinatorik ist ein Zweig der Mathematik, der sich mit der Frage beschäftigt, wie viele verschiedene Kombinationen unter bestimmten Bedingungen aus gegebenen Objekten hergestellt werden können. Die Grundlagen der Kombinatorik sind für die Schätzung der Wahrscheinlichkeiten zufälliger Ereignisse sehr wichtig, weil Sie ermöglichen es uns, die grundsätzlich mögliche Zahl zu berechnen Verschiedene Optionen Entwicklungen von Ereignissen.
Grundformel der Kombinatorik
Es gebe k Gruppen von Elementen und i-te Gruppe besteht aus n i Elementen. Wählen wir aus jeder Gruppe ein Element aus. Dann Gesamtzahl Die N Möglichkeiten, auf denen eine solche Wahl getroffen werden kann, werden durch die Beziehung N=n 1 *n 2 *n 3 *...*n k bestimmt.
Beispiel 1. Lassen Sie uns diese Regel anhand eines einfachen Beispiels erklären. Es gebe zwei Gruppen von Elementen, und die erste Gruppe besteht aus n 1 Elementen und die zweite aus n 2 Elementen. Wie viele verschiedene Elementpaare können aus diesen beiden Gruppen gebildet werden, sodass das Paar ein Element aus jeder Gruppe enthält? Nehmen wir an, wir haben das erste Element aus der ersten Gruppe genommen und, ohne es zu ändern, alle möglichen Paare durchgegangen und nur die Elemente aus der zweiten Gruppe geändert. Für dieses Element kann es n 2 solcher Paare geben. Dann nehmen wir das zweite Element aus der ersten Gruppe und bilden auch alle möglichen Paare dafür. Es wird auch n 2 solcher Paare geben. Da es in der ersten Gruppe nur n 1 Elemente gibt, sind die insgesamt möglichen Optionen n 1 *n 2 .
Beispiel 2. Wie viele dreistellige gerade Zahlen können aus den Ziffern 0, 1, 2, 3, 4, 5, 6 gebildet werden, wenn die Ziffern wiederholt werden können?
Lösung: n 1 =6 (weil Sie als erste Ziffer eine beliebige Zahl von 1, 2, 3, 4, 5, 6 annehmen können), n 2 =7 (weil Sie als zweite Ziffer eine beliebige Zahl von 0 annehmen können, 1, 2 , 3, 4, 5, 6), n 3 =4 (da jede Zahl von 0, 2, 4, 6 als dritte Ziffer angenommen werden kann).
Also, N=n 1 *n 2 *n 3 =6*7*4=168.
Für den Fall, dass alle Gruppen aus der gleichen Anzahl von Elementen bestehen, d.h. n 1 =n 2 =...n k =n Wir können davon ausgehen, dass jede Auswahl aus derselben Gruppe erfolgt und das Element nach der Auswahl an die Gruppe zurückgegeben wird. Dann ist die Anzahl aller Auswahlmethoden n k . Diese Auswahlmethode in der Kombinatorik wird aufgerufen Proben mit Rückgabe.
Beispiel 3. Wie viele vierstellige Zahlen lassen sich aus den Ziffern 1, 5, 6, 7, 8 bilden?
Lösung. Für jede Ziffer einer vierstelligen Zahl gibt es fünf Möglichkeiten, das heißt N=5*5*5*5=5 4 =625.
Betrachten Sie eine Menge bestehend aus n Elementen. In der Kombinatorik heißt diese Menge Durchschnittsbevölkerung.
Anzahl der Platzierungen von n Elementen pro m
Definition 1. Unterkunft ab N Elemente von M in der Kombinatorik irgendein bestelltes Set aus M verschiedene Elemente, ausgewählt aus der Bevölkerung in N Elemente.
Beispiel 4. Unterschiedliche Anordnungen von drei Elementen (1, 2, 3) durch zwei ergeben die Mengen (1, 2), (2, 1), (1, 3), (3, 1), (2, 3), (3 , 2 ). Platzierungen können sich sowohl in den Elementen als auch in der Reihenfolge voneinander unterscheiden.
Die Anzahl der Platzierungen in der Kombinatorik wird mit A n m bezeichnet und nach der Formel berechnet:
Kommentar: n!=1*2*3*...*n (sprich: „en faktoriell“), außerdem wird angenommen, dass 0!=1.
Beispiel 5. Wie viele zweistellige Zahlen gibt es, bei denen die Zehnerstelle und die Einerstelle unterschiedlich und ungerade sind?
Lösung: Weil Wenn es fünf ungerade Ziffern gibt, nämlich 1, 3, 5, 7, 9, dann besteht diese Aufgabe darin, zwei der fünf verschiedenen Ziffern auszuwählen und an zwei verschiedenen Positionen zu platzieren, d. h. Die angegebenen Zahlen lauten:
Definition 2. Kombination aus N Elemente von M in der Kombinatorik irgendein ungeordnete Menge aus M verschiedene Elemente, ausgewählt aus der Bevölkerung in N Elemente.
Beispiel 6. Für die Menge (1, 2, 3) sind die Kombinationen (1, 2), (1, 3), (2, 3).
Anzahl der Kombinationen von n Elementen, jeweils m
Die Anzahl der Kombinationen wird mit C n m bezeichnet und nach folgender Formel berechnet:
Beispiel 7. Auf wie viele Arten kann ein Leser zwei von sechs verfügbaren Büchern auswählen?
Lösung: Die Anzahl der Methoden entspricht der Anzahl der Kombinationen von sechs Zweierbüchern, d. h. entspricht:
Permutationen von n Elementen
Definition 3. Permutation aus N Elemente heißen beliebig bestelltes Set diese Elemente.
Beispiel 7a. Alle möglichen Permutationen einer Menge bestehend aus drei Elementen (1, 2, 3) sind: (1, 2, 3), (1, 3, 2), (2, 3, 1), (2, 1, 3) , ( 3, 2, 1), (3, 1, 2).
Die Anzahl der verschiedenen Permutationen von n Elementen wird mit P n bezeichnet und nach der Formel P n =n! berechnet.
Beispiel 8. Auf wie viele Arten lassen sich sieben Bücher verschiedener Autoren in einer Reihe in einem Regal anordnen?
Lösung: Bei diesem Problem geht es um die Anzahl der Permutationen sieben verschiedene Bücher. Es gibt P 7 =7!=1*2*3*4*5*6*7=5040 Möglichkeiten, die Bücher anzuordnen.
Diskussion. Wir sehen, dass die Anzahl der möglichen Kombinationen nach unterschiedlichen Regeln (Permutationen, Kombinationen, Platzierungen) berechnet werden kann und das Ergebnis unterschiedlich sein wird, weil Das Berechnungsprinzip und die Formeln selbst sind unterschiedlich. Wenn Sie sich die Definitionen genau ansehen, werden Sie feststellen, dass das Ergebnis von mehreren Faktoren gleichzeitig abhängt.
Erstens, aus wie vielen Elementen wir ihre Mengen kombinieren können (wie groß ist die Gesamtheit der Elemente).
Zweitens hängt das Ergebnis von der Größe der benötigten Elementmengen ab.
Schließlich ist es wichtig zu wissen, ob die Reihenfolge der Elemente in der Menge für uns von Bedeutung ist. Lassen Sie uns den letzten Faktor anhand des folgenden Beispiels erklären.
Beispiel 9. An Elternabend 20 Personen sind anwesend. Wie viele verschiedene Möglichkeiten gibt es für die Zusammensetzung des Elternbeirats, wenn dieser aus 5 Personen bestehen muss?
Lösung: In diesem Beispiel interessiert uns nicht die Reihenfolge der Namen auf der Ausschussliste. Wenn sich dadurch herausstellt, dass dieselben Personen Teil davon sind, dann ist dies für uns im Sinne der gleichen Option. Daher können wir die Formel verwenden, um die Zahl zu berechnen Kombinationen von 20 Elementen je 5.
Anders verhält es sich, wenn jedes Gremiumsmitglied zunächst für einen bestimmten Arbeitsbereich zuständig ist. Dann sind bei gleicher Listenzusammensetzung des Ausschusses möglicherweise 5 Personen darin! Optionen Permutationen diese Angelegenheit. Die Anzahl der unterschiedlichen (sowohl in der Zusammensetzung als auch im Verantwortungsbereich) Optionen wird in diesem Fall durch die Anzahl bestimmt Platzierungen von 20 Elementen je 5.
Selbsttestaufgaben
1. Wie viele dreistellige gerade Zahlen können aus den Ziffern 0, 1, 2, 3, 4, 5, 6 gebildet werden, wenn die Ziffern wiederholt werden können?
Weil Eine gerade Zahl an dritter Stelle kann 0, 2, 4, 6 sein, d. h. vier Stellen. Die zweite Stelle kann eine beliebige der sieben Ziffern sein. Die erste Stelle kann eine beliebige der sieben Ziffern außer Null sein, d. h. 6 Möglichkeiten. Ergebnis =4*7*6=168.
2. Wie viele fünfstellige Zahlen gibt es, die von links nach rechts und von rechts nach links gleich gelesen werden?
Die erste Stelle kann eine beliebige Zahl außer 0 sein, d.h. 9 Möglichkeiten. An zweiter Stelle kann jede beliebige Zahl stehen, d.h. 10 Möglichkeiten. Die dritte Stelle kann auch eine beliebige Zahl sein, also 10 Möglichkeiten. Die vierte und fünfte Ziffer sind vorgegeben, sie stimmen mit der ersten und zweiten überein, daher beträgt die Anzahl dieser Ziffern 9*10*10=900.
3. Die Klasse besteht aus zehn Fächern und fünf Unterrichtsstunden pro Tag. Auf wie viele Arten kann man einen Zeitplan für einen Tag erstellen?
4. Auf wie viele Arten können 4 Delegierte für eine Konferenz ausgewählt werden, wenn die Gruppe aus 20 Personen besteht?
n = C 20 4 = (20!)/(4!*(20-4)!)=(16!*17*18*19*20)/((1*2*3*4)*(16! ))=(17*18*19*20)/(1*2*3*4)=4845.
5. Auf wie viele Arten können acht verschiedene Briefe in acht verschiedene Umschläge gesteckt werden, wenn in jeden Umschlag nur ein Brief gesteckt wird?
Sie können einen der acht Briefe in den ersten Umschlag stecken, einen der restlichen sieben in den zweiten, einen der sechs in den dritten usw. n = 8! = 1*2*3*4*5*6*7*8 = 40320.
6. Eine Kommission bestehend aus zwei Mathematikern und sechs Wirtschaftswissenschaftlern soll aus drei Mathematikern und zehn Wirtschaftswissenschaftlern bestehen. Auf wie viele Arten kann dies geschehen?
