Freunde! Da ich dieses tote Notizbuch bereits habe, nutze ich es, um Ihnen ein Problem zu stellen, mit dem gestern drei Physiker, zwei Wirtschaftswissenschaftler, einer von der Polytechnischen Hochschule und einer von den Geisteswissenschaften zu kämpfen hatten. Wir haben unser ganzes Gehirn kaputt gemacht und wir bekommen ständig andere Ergebnisse. Vielleicht gibt es unter euch Programmierer und mathematische Genies, außerdem ist das Problem generell schulisch und sehr einfach, wir haben nur keine Formel. Weil wir die exakten Wissenschaften aufgegeben haben und stattdessen aus irgendeinem Grund Bücher schreiben und Bilder zeichnen. Es tut uns leid.

Also Vorgeschichte.

Ich bekam eine neue Bankkarte und wie üblich erriet ich mühelos ihren PIN-Code. Aber nicht hintereinander. Sagen wir mal, der PIN-Code war 8794 und ich habe 9748 angerufen. Das heißt, ich triumphierte alle Zahlen erraten in der angegebenen vierstelligen Zahl enthalten. Nun ja, nicht nur eine Zahl, aber eben seine Komponenten bei fragte sich. Aber die Zahlen stimmen alle! ANMERKUNG - Ich habe nach dem Zufallsprinzip gehandelt, das heißt, ich musste die bereits bekannten Zahlen nicht in die richtige Reihenfolge bringen, ich habe nur im Geiste gehandelt: Hier gibt es vier mir unbekannte Zahlen, und ich glaube, dass darunter einige sein können 9, 7, 4 und 8 sein, 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 genommen und erraten habe). Das heißt, aus wie vielen Kombinationen von vier Zahlen musste ich wählen? Und dann begann natürlich die Hölle. Unsere Köpfe explodierten den ganzen Abend, und jeder kam als Ergebnis auf ganz andere Antworten! Ich fing sogar an, alle diese Kombinationen hintereinander in ein Notizbuch zu schreiben, als sie zunahmen, aber bei vierhundert stellte ich fest, dass es mehr als vierhundert waren (jedenfalls widerlegte dies die Antwort des Physikers Thresh, der versicherte mir, dass es vierhundert Kombinationen waren, aber es ist immer noch nicht ganz klar) - und gab auf.

Es kann passieren, dass es auch eine Superzahl ins Spiel schafft, muss es aber nicht. Der Unterschied zwischen einer Permutation von Wörtern oder einer Kombination liegt hauptsächlich in der Reihenfolge, in der wir die Elemente platzieren, aus denen die Menge besteht. Wenn die Reihenfolge, in der sich die Elemente der Menge befinden, keine Rolle spielt, werden wir sagen, dass es sich um eine Kombination handelt.

Banane - Erdbeeren - Äpfel od. Wenn die Reihenfolge der Elemente einer Menge wichtig ist, dann sprechen wir von einer Permutation. Zum Beispiel, wenn wir den Tresorschlüssel verwenden. Es ist unmöglich, dass es geöffnet werden kann, wenn wir es verwenden. Permutationen, bei denen Elemente einer Menge wiederholt werden dürfen.

Eigentlich, Kern der Frage. Wie groß ist die Wahrscheinlichkeit, die vier Zahlen einer vierstelligen Zahl (in beliebiger Reihenfolge) zu erraten?

Oder nicht, formulieren wir um (ich bin Humanist, sorry, obwohl ich immer eine große Schwäche für Mathematik hatte), um es klarer und klarer zu machen. Wie nicht wiederkehrend Zahlenkombinationen, die in einer Reihe von Ordnungszahlen von 0 bis 9999 enthalten sind? ( Bitte verwechseln Sie dies nicht mit der Frage "wie viele Kombinationen nicht wiederkehrend Nummern"!!! Zahlen können wiederholt werden! Ich meine, 2233 und 3322 sind in diesem Fall die gleiche Kombination!!).

Im Sicherheitsbeispiel könnte der Schlüssel 8 8 8 sein. Wenn wir wissen wollen, wie viele Permutationen wir mit Wiederholungen bekommen können, um den Schlüssel in den Safe zu legen, dann müssen wir überlegen, wie viele Elemente in jeder der Positionen platziert werden können . Das bedeutet, dass wir jede der 10 Zahlen an der ersten Position platzieren können, jede der 10 Zahlen an der zweiten und jede der 10 Zahlen an der dritten, also haben wir.

In die erste Position können wir eine von 10 Zahlen von 0 bis eintragen. Für die zweite Position können wir jede andere Zahl als die, die an der ersten Position platziert wurde, d.h. jede der 9 verbleibenden Zahlen einsetzen. Bestimmen, wie man in Kombination bestellt.

Oder genauer gesagt. Ich muss viermal eine Zahl von zehn erraten. Aber nicht hintereinander.

Naja, oder was anderes. Im Allgemeinen müssen Sie herausfinden, wie viele Optionen für die Zahlenkombination ich hatte, die den PIN-Code der Karte bildete. Hilfe, gute Leute! Nur bitte, helfen Sie, fangen Sie nicht sofort an zu schreiben, dass es 9999 Optionen dafür gibt(gestern kam das allen zuerst in den Sinn), weil das Unsinn ist - schließlich sind in der Perspektive, die uns beunruhigt, die Nummer 1234, die Nummer 3421, die Nummer 4312 und so weiter ein und das selbe! Nun, ja, die Zahlen können sich wiederholen, denn es gibt einen PIN-Code 1111 oder dort zum Beispiel 0007. Sie können sich anstelle eines PIN-Codes eine Autonummer vorstellen. Angenommen, wie hoch ist die Wahrscheinlichkeit, alle einzelnen Ziffern zu erraten, aus denen die Autonummer besteht? Oder, um die Wahrscheinlichkeitstheorie ganz zu eliminieren - aus wie vielen Zahlenkombinationen musste ich eine auswählen?

Wir bestimmen, auf wie viele Arten wir eine Gruppe von r-Elementen anordnen können. Schließlich wenden wir die folgende Formel an. Es gibt 8 Personen, um einen Ausschuss von fünf zu bilden. Wie viele verschiedene Möglichkeiten gibt es, einen Ausschuss zu bilden? Es ist eine Kombination, weil die Reihenfolge der Ausschussmitglieder keine Rolle spielt.

Position 1 kann eines der 8 Komiteemitglieder sein. Da jedes Mitglied des Komitees jeweils nur eine Position einnehmen kann, kann jedes der anderen 7 Mitglieder die zweite Position einnehmen. Die dritte Position kann nur von einem der verbleibenden 6 Mitglieder kommen, und so weiter.

Bitte untermauern Sie Ihre Antworten und Argumente mit einigen genauen Formeln, denn gestern haben wir fast den Verstand verloren. Vielen Dank im Voraus an alle!

P.S. Eine kluge Person, ein Programmierer, ein Künstler und ein Erfinder, hat die Probleme gerade sehr richtig vorgeschlagen und mir ein paar Minuten gute Laune beschert: " die lösung des problemes ist folgende: sie hat eine zwangsstörung, die behandlung ist folgende: heiraten und tomaten spießen. Wenn ich an ihrer Stelle wäre, würde mich eher nicht die Frage „wie hoch ist die Wahrscheinlichkeit“ beschäftigen, sondern die Frage „achte ich verdammt noch mal auf all diese Zahlen“? Im Allgemeinen gibt es nichts hinzuzufügen :)

Wir geben an, dass das Komitee nur aus 5 Mitgliedern bestehen wird, wir bestimmen, auf wie viele Arten wir eine Gruppe von 5 Elementen bestellen können. Da das Komitee aus 5 Mitgliedern besteht, 8 die in diesem Komitee sein können, müssen wir. 8-5 = 3 und wir haben berechnet, wie diese 3 verbleibenden Mitglieder bestellt werden könnten.

Wenden wir abschließend die Formel an. Frage: Auf wie viele verschiedene Arten kann man 16 Billardkugeln bestellen? Denken Sie daran, dass jede Kugel eine Position einnehmen kann. Wenn beispielsweise eine 14er Kugel an der ersten Position erscheint, kann diese Kugel keine andere Position mehr einnehmen.

Die Quelle des Berichts könnte nicht zuverlässiger sein. In der Schulmappe haben wir vier Bücher mit verschiedenen Fächern, die von oben nach unten gestapelt sind genaue Reihenfolge. Portugiesisch, Mathematik, Geschichte und Geographie. Wie viele solcher Bücher können in dieser Brieftasche gesammelt werden, einschließlich der aktuellen Bestellung?

Der unten stehende Rechner wurde entwickelt, um alle Kombinationen von n mal m Elementen zu generieren.
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 den Ordnungsindizes der Elemente der Menge.
Betrachten wir den Algorithmus anhand eines Beispiels.
Betrachten Sie zur einfacheren Darstellung einen Satz von fünf Elementen, deren Indizes mit 1 beginnen, nämlich 1 2 3 4 5.
Es müssen alle Kombinationen der Größe m = 3 generiert werden.
Zuerst wird die erste Kombination der gegebenen Größe m 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 es um 1 erhöht.
1 2 4
Das letzte Element wird erneut überprüft und erneut inkrementiert.
1 2 5
Jetzt ist der Wert des Elements gleich dem maximal möglichen: n - m + i = 5 - 3 + 3 = 5, das vorherige Element mit i = 2 wird geprüft.
Wenn sein Wert kleiner als n - m + i ist, wird er um 1 erhöht, und für alle folgenden Elemente ist der Wert gleich dem Wert des vorherigen Elements plus 1.
1 (2+1)3 (3+1)4 = 1 3 4
Dann prüfen wir wieder auf i = 3.
1 3 5
Dann - überprüfe auf i = 2.
1 4 5
Dann kommt die Wende i = 1.
(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.

Denken wir über dieses Problem nach. Bei der Auswahl des ersten Buches, das in das Portfolio aufgenommen werden soll, haben wir 4 Möglichkeiten, da wir noch keine Bücher darin platziert haben, haben wir vier Bücher zur Auswahl: Portugiesisch, Mathematik, Geschichte und Geographie.

Wenn wir die Sammlung mit einem portugiesischen Buch beginnen, haben wir bei der Auswahl des nächsten Buches, das darin platziert werden soll, 3 Möglichkeiten: Mathematik, Geschichte und Geographie. Wenn wir das Geschichtsbuch als zweites Buch des Stapels auswählen, haben wir für das dritte Buch nur zwei Möglichkeiten: Mathematik und Erdkunde.

Die Kombinatorik ist ein Zweig der Mathematik, der sich mit der Frage befasst, wie viele verschiedene Kombinationen unter bestimmten Bedingungen aus gegebenen Objekten gemacht werden können. Die Grundlagen der Kombinatorik sind sehr wichtig, um die Wahrscheinlichkeiten von Zufallsereignissen abzuschätzen, weil sie erlauben uns, die grundsätzlich mögliche Zahl zu berechnen Verschiedene Optionen Entwicklung von Veranstaltungen.

Grundformel der Kombinatorik

Seien k Gruppen von Elementen, und i-te Gruppe besteht aus n i Elementen. Lassen Sie uns ein Element aus jeder Gruppe auswählen. Dann wird die Gesamtzahl N von Wegen, auf denen eine solche Wahl getroffen werden kann, durch die Beziehung N = n 1 *n 2 *n 3 *...*n k bestimmt.

Beispiel 1 Lassen Sie uns diese Regel an einem einfachen Beispiel erläutern. Lassen Sie es zwei Gruppen von Elementen geben, 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? Angenommen, wir nehmen das erste Element aus der ersten Gruppe und gehen alle möglichen Paare durch, ohne es zu ändern, und ändern nur die Elemente aus der zweiten Gruppe. Es gibt n 2 solcher Paare für dieses Element. 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, gibt es n 1 *n 2 mögliche Optionen.

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 \u003d 6 (da Sie jede Ziffer von 1, 2, 3, 4, 5, 6 als erste Ziffer nehmen können), n 2 \u003d 7 (da Sie jede Ziffer von 0 als zweite Ziffer nehmen können , 1 , 2, 3, 4, 5, 6), n 3 \u003d 4 (da Sie jede Ziffer von 0, 2, 4, 6 als dritte Ziffer nehmen können).
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 können wir davon ausgehen, dass jede Auswahl aus derselben Gruppe erfolgt und das Element nach der Auswahl in die Gruppe zurückkehrt. Dann ist die Anzahl aller Wahlmöglichkeiten gleich n k . Diese Art der Wahl heißt in der Kombinatorik Proben zurücksenden.

Beispiel 3 Wie viele vierstellige Zahlen lassen sich aus den Zahlen 1, 5, 6, 7, 8 bilden?
Lösung. Für jede Ziffer einer vierstelligen Zahl gibt es fünf Möglichkeiten, also N=5*5*5*5=5 4 =625.

Stellen Sie sich eine Menge vor, die aus n Elementen besteht. Diese Menge heißt in der Kombinatorik Durchschnittsbevölkerung.

Anzahl der Platzierungen von n Elementen mal m

Bestimmung 1. Unterkunft ab n Elemente von m in der Kombinatorik heißt beliebig bestellter Satz aus m verschiedene Elemente, ausgewählt aus der allgemeinen Bevölkerung in n Elemente.

Beispiel 4 Verschiedene Anordnungen von drei Elementen (1, 2, 3) zwei mal zwei werden zu Sätzen (1, 2), (2, 1), (1, 3), (3, 1), (2, 3), (3). , 2 ). Platzierungen können sich sowohl in Elementen als auch in ihrer Reihenfolge voneinander unterscheiden.

Die Anzahl der Platzierungen in der Kombinatorik wird mit A n m bezeichnet und berechnet sich nach der Formel:

Kommentar: n!=1*2*3*...*n (sprich: "en factorial"), 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 es fünf ungerade Ziffern gibt, nämlich 1, 3, 5, 7, 9, dann reduziert sich dieses Problem darauf, zwei der fünf verschiedenen Ziffern auszuwählen und an zwei verschiedenen Positionen zu platzieren, d.h. Die angegebenen Zahlen sind:

Definition 2. Kombination aus n Elemente von m in der Kombinatorik heißt beliebig ungeordneter Satz aus m verschiedene Elemente, ausgewählt aus der allgemeinen 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 mal m

Die Anzahl der Kombinationen wird mit C n m bezeichnet und errechnet sich nach der Formel:

Beispiel 7 Auf wie viele Arten kann der Leser zwei von sechs verfügbaren Büchern auswählen?

Lösung: Die Anzahl der Wege ist gleich der Anzahl der Kombinationen von sechs Büchern mal zwei, d.h. gleich:

Permutationen von n Elementen

Definition 3. Permutation aus n Elemente heißt beliebig bestellter Satz 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 durch die Formel P n = n! berechnet.

Beispiel 8 Auf wie viele Arten können sieben Bücher verschiedener Autoren in einem Regal aneinandergereiht werden?

Lösung: Bei diesem Problem geht es um die Anzahl der Permutationen von sieben verschiedenen Büchern. 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 verschiedenen Regeln (Permutationen, Kombinationen, Platzierungen) berechnet werden kann und das Ergebnis unterschiedlich sein wird, weil das Zählprinzip und die Formeln selbst sind unterschiedlich. Schaut man sich die Definitionen genau an, erkennt man, dass das Ergebnis von mehreren Faktoren gleichzeitig abhängt.

Erstens, aus wie vielen Elementen können wir ihre Mengen kombinieren (wie groß ist die allgemeine Population von Elementen).

Zweitens hängt das Ergebnis davon ab, welche Elementmengen wir benötigen.

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 erläutern.

Beispiel 9 Beim Elternabend sind 20 Personen anwesend. Wie viele verschiedene Möglichkeiten für die Zusammensetzung des Elternbeirats gibt es, wenn dieser aus 5 Personen bestehen soll?
Lösung: In diesem Beispiel interessiert uns nicht die Reihenfolge der Namen auf der Komiteeliste. Wenn infolgedessen dieselben Personen in seiner Zusammensetzung vorkommen, dann ist dies für uns von der Bedeutung her dieselbe Option. Daher können wir die Formel verwenden, um die Zahl zu berechnen Kombinationen von 20 Elementen, 5.

Anders sieht es aus, wenn jedes Mitglied des Gremiums zunächst für einen bestimmten Arbeitsbereich zuständig ist. Dann sind bei gleicher Gehaltsliste des Komitees 5 darin möglich! Optionen Permutationen diese Angelegenheit. Die Anzahl der unterschiedlichen (sowohl hinsichtlich der Zusammensetzung als auch des Aufgabenbereichs) Optionen wird in diesem Fall durch die Anzahl bestimmt Platzierungen von 20 Elementen, 5.

Aufgaben zum Selbsttest
1. Wie viele dreistellige gerade Zahlen lassen sich aus den Zahlen 0, 1, 2, 3, 4, 5, 6 bilden, wenn sich die Zahlen wiederholen können?

2. Wie viele fünfstellige Zahlen gibt es, die von links nach rechts und von rechts nach links gleich lauten?

3. Es gibt zehn Fächer in der Klasse und fünf Unterrichtsstunden pro Tag. Auf wie viele Arten können Sie einen Zeitplan für einen Tag erstellen?

4. Auf wie viele Arten können 4 Delegierte für die Konferenz ausgewählt werden, wenn die Gruppe 20 Personen umfasst?

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?

6. Aus drei Mathematikern und zehn Ökonomen ist eine Kommission zu bilden, die aus zwei Mathematikern und sechs Ökonomen besteht. Auf wie viele Arten kann dies geschehen?

Freunde! Da ich dieses tote Notizbuch bereits habe, nutze ich es, um Ihnen ein Problem zu stellen, mit dem gestern drei Physiker, zwei Wirtschaftswissenschaftler, einer von der Polytechnischen Hochschule und einer von den Geisteswissenschaften zu kämpfen hatten. Wir haben unser ganzes Gehirn kaputt gemacht und wir bekommen ständig andere Ergebnisse. Vielleicht gibt es unter euch Programmierer und mathematische Genies, außerdem ist das Problem generell schulisch und sehr einfach, wir haben nur keine Formel. Weil wir die exakten Wissenschaften aufgegeben haben und stattdessen aus irgendeinem Grund Bücher schreiben und Bilder zeichnen. Es tut uns leid.

Also Vorgeschichte.

Ich bekam eine neue Bankkarte und wie üblich erriet ich mühelos ihren PIN-Code. Aber nicht hintereinander. Sagen wir mal, der PIN-Code war 8794 und ich habe 9748 angerufen. Das heißt, ich triumphierte alle Zahlen erraten in der angegebenen vierstelligen Zahl enthalten. Nun ja, nicht nur eine Zahl, aber eben seine Komponenten bei fragte sich. Aber die Zahlen stimmen alle! ANMERKUNG - Ich habe nach dem Zufallsprinzip gehandelt, das heißt, ich musste die bereits bekannten Zahlen nicht in die richtige Reihenfolge bringen, ich habe nur im Geiste gehandelt: Hier gibt es vier mir unbekannte Zahlen, und ich glaube, dass darunter einige sein können 9, 7, 4 und 8 sein, 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 genommen und erraten habe). Das heißt, aus wie vielen Kombinationen von vier Zahlen musste ich wählen? Und dann begann natürlich die Hölle. Unsere Köpfe explodierten den ganzen Abend, und am Ende kamen alle absolut raus verschiedene Varianten Antworten! Ich fing sogar an, alle diese Kombinationen hintereinander in ein Notizbuch zu schreiben, als sie zunahmen, aber bei vierhundert stellte ich fest, dass es mehr als vierhundert waren (jedenfalls widerlegte dies die Antwort des Physikers Thresh, der versicherte mir, dass es vierhundert Kombinationen waren, aber es ist immer noch nicht ganz klar) - und gab auf.

Eigentlich, Kern der Frage. Wie groß ist die Wahrscheinlichkeit, die vier Zahlen einer vierstelligen Zahl (in beliebiger Reihenfolge) zu erraten?

Oder nicht, formulieren wir um (ich bin Humanist, sorry, obwohl ich immer eine große Schwäche für Mathematik hatte), um es klarer und klarer zu machen. Wie nicht wiederkehrend Zahlenkombinationen, die in einer Reihe von Ordnungszahlen von 0 bis 9999 enthalten sind? ( Bitte verwechseln Sie dies nicht mit der Frage "wie viele Kombinationen nicht wiederkehrend Nummern"!!! Zahlen können wiederholt werden! Ich meine, 2233 und 3322 sind in diesem Fall die gleiche Kombination!!).

Oder genauer gesagt. Ich muss viermal eine Zahl von zehn erraten. Aber nicht hintereinander.

Naja, oder was anderes. Im Allgemeinen müssen Sie herausfinden, wie viele Optionen für die Zahlenkombination ich hatte, die den PIN-Code der Karte bildete. Hilfe, gute Leute! Nur bitte, helfen Sie, fangen Sie nicht sofort an zu schreiben, dass es 9999 Optionen dafür gibt(gestern kam das allen zuerst in den Sinn), weil das Unsinn ist - schließlich sind in der Perspektive, die uns beunruhigt, die Nummer 1234, die Nummer 3421, die Nummer 4312 und so weiter ein und das selbe! Nun, ja, die Zahlen können sich wiederholen, denn es gibt einen PIN-Code 1111 oder dort zum Beispiel 0007. Sie können sich anstelle eines PIN-Codes eine Autonummer vorstellen. Angenommen, wie hoch ist die Wahrscheinlichkeit, alle einzelnen Ziffern zu erraten, aus denen die Autonummer besteht? Oder, um die Wahrscheinlichkeitstheorie ganz zu eliminieren - aus wie vielen Zahlenkombinationen musste ich eine auswählen?

Bitte untermauern Sie Ihre Antworten und Argumente mit einigen genauen Formeln, denn gestern haben wir fast den Verstand verloren. Vielen Dank im Voraus an alle!

P.S. Eine kluge Person, Programmierer, Künstler und Erfinder, hat gerade sehr richtig vorgeschlagen die richtige Entscheidung Probleme, die mir ein paar Minuten gute Laune bescheren: " die lösung des problemes ist folgende: sie hat eine zwangsstörung, die behandlung ist folgende: heiraten und tomaten spießen. Wenn ich an ihrer Stelle wäre, würde mich eher nicht die Frage „wie hoch ist die Wahrscheinlichkeit“ beschäftigen, sondern die Frage „achte ich verdammt noch mal auf all diese Zahlen“? Im Allgemeinen gibt es nichts hinzuzufügen :)

Der unten stehende Rechner wurde entwickelt, um alle Kombinationen von n mal m Elementen zu generieren.
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 den Ordnungsindizes der Elemente der Menge.
Betrachten wir den Algorithmus anhand eines Beispiels.
Betrachten Sie zur einfacheren Darstellung einen Satz von fünf Elementen, deren Indizes mit 1 beginnen, nämlich 1 2 3 4 5.
Es müssen alle Kombinationen der Größe m = 3 generiert werden.
Zuerst wird die erste Kombination der gegebenen Größe m 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 es um 1 erhöht.
1 2 4
Das letzte Element wird erneut überprüft und erneut inkrementiert.
1 2 5
Jetzt ist der Wert des Elements gleich dem maximal möglichen: n - m + i = 5 - 3 + 3 = 5, das vorherige Element mit i = 2 wird geprüft.
Wenn sein Wert kleiner als n - m + i ist, wird er um 1 erhöht, und für alle folgenden Elemente ist der Wert gleich dem Wert des vorherigen Elements plus 1.
1 (2+1)3 (3+1)4 = 1 3 4
Dann prüfen wir wieder auf i = 3.
1 3 5
Dann - überprüfe auf i = 2.
1 4 5
Dann kommt die Wende i = 1.
(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 PINs in der weltweiten Infrastruktur wurde bisher noch keine akademische Forschung darüber durchgeführt, wie Menschen tatsächlich PINs auswählen.

Die Forscher der University of Cambridge, Sören Preibusch und Ross Anderson, korrigierten die Situation, indem sie die weltweit erste quantitative Analyse der Schwierigkeit veröffentlichten, eine vierstellige Bank-PIN zu erraten.

Anhand von Daten zu Passwortlecks aus Nichtbankenquellen und Online-Umfragen fanden die Forscher heraus, dass Benutzer die Wahl von PIN-Codes viel ernster nehmen als die Wahl von Passwörtern für Websites: Die meisten Codes enthalten eine fast zufällige Kombination von Zahlen. Unter den Ausgangsdaten gibt es jedoch auch einfache Kombinationen, und Geburtstage - das heißt, mit etwas Glück kann ein Angreifer den begehrten Code einfach erraten.

Ausgangspunkt der Studie war eine Reihe von 4-stelligen Passwortsequenzen aus der RockYou-Datenbank (1,7 Millionen) und eine Datenbank mit 200.000 PIN-Codes aus dem Sperrprogramm iPhone-Bildschirm(Die Basis wurde vom Anwendungsentwickler Daniel Amitay bereitgestellt). Die aus diesen Daten erstellten Diagramme zeigen interessante Muster – Daten, Jahre, wiederholte Zahlen und sogar PIN-Codes, die auf 69 enden. Basierend auf diesen Beobachtungen erstellten Wissenschaftler ein lineares Regressionsmodell, das die Popularität jeder PIN in Abhängigkeit von 25 Faktoren schätzt, wie z ob der Code ein Datum im TTMM-Format ist, ob es sich um eine aufsteigende Folge handelt und so weiter. Diese Rahmenbedingungen erfüllen jeweils 79 % bzw. 93 % der PIN-Codes in den Sets.

Benutzer wählen also 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. In Ermangelung eines großen Satzes echter Bankdaten befragten die Forscher mehr als 1.300 Personen, um zu beurteilen, wie sich echte PIN-Codes von den bereits berücksichtigten unterscheiden. Aufgrund der Besonderheiten der Studie wurden die Befragten nicht nach den Codes selbst gefragt, sondern nur nach ihrer Einhaltung eines der oben genannten Faktoren (Erhöhung, DDMM-Format usw.).

Es stellte sich heraus, dass die Leute bei der Auswahl von Bank-PIN-Codes wirklich viel vorsichtiger sind. Etwa ein Viertel der Befragten verwendet eine von einer Bank generierte zufällige PIN. Mehr als ein Drittel wählt seine PIN anhand einer alten Telefonnummer, Studenten-ID-Nummer oder einer anderen Zahlenkombination, die zufällig aussieht. Den Ergebnissen zufolge verwenden 64 % der Karteninhaber einen Pseudo-Zufalls-PIN-Code, was viel mehr ist als 23-27 % in früheren Experimenten mit Nicht-Bankcodes. Weitere 5 % verwenden ein Zahlenmuster (z. B. 4545) und 9 % bevorzugen ein Tastaturmuster (z. B. 2684). Im Allgemeinen hat ein Angreifer mit sechs Versuchen (drei mit einem Geldautomaten und drei mit einem Zahlungsterminal) eine Chance von weniger als 2 %, die Karten-PIN einer anderen Person zu erraten.

Faktor	Beispiel	rock dich	IPhone	Interview
Termine
DDMM	2311	5.26	1.38	3.07
DMYJ	3876	9.26	6.46	5.54
MMTT	1123	10.00	9.35	3.66
mmyy	0683	0.67	0.20	0.94
JJJJ	1984	33.39	7.12	4.95
Gesamt		58.57	24.51	22.76
Tastaturmuster
verbunden	6351	1.52	4.99	-
Quadrat	1425	0.01	0.58	-
Ecken	9713	0.19	1.06	-
Kreuz	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	-
wiederkehrende Paare	2525	2.31	4.11	-
gleichen Ziffern	6666	0.40	6.67	-
absteigende Folge	3210	0.13	0.29	-
aufsteigende Reihenfolge	4567	3.83	4.52	-
Gesamt		15.16	24.85	4.60
Zufälliger Satz von Zahlen		23.17	27.67	63.68

Alles wäre gut, 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. Damit ändert sich die Sache erheblich, denn fast alle (99%) Befragten antworteten, dass sie es in ihrem Portemonnaie mitnehmen Bankkarten diverse Ausweise, auf denen dieses Datum aufgedruckt ist. Wenn ein Angreifer den Geburtstag des Karteninhabers kennt, steigt die Wahrscheinlichkeit, den PIN-Code zu erraten, bei einem kompetenten Vorgehen auf 9 %.

Die 100 beliebtesten PINs

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, Ihre PIN auszuspionieren, als sie zu erraten. Aber man kann sich auch vor dem Gucken schützen - auch in scheinbar aussichtslosen Situationen:

Alle N Elemente, und keines wiederholt sich, dann ist dies das Problem der Anzahl der Permutationen. Die Lösung ist einfach zu finden. Jedes der N Elemente kann den ersten Platz in der Zeile einnehmen, daher werden N Optionen erhalten. Auf dem zweiten Platz - jeder, außer dem, der bereits für den ersten Platz verwendet wurde. Daher gibt es für jede der bereits gefundenen N Optionen (N – 1) zweitplatzierte Optionen, und die Gesamtzahl der Kombinationen wird N*(N – 1).
Dasselbe kann für die restlichen Elemente der Reihe wiederholt werden. Für den allerletzten Platz gibt es nur noch eine Option – das letzte verbleibende Element. Für den vorletzten - zwei Optionen 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 heißt Fakultät von N und wird mit N bezeichnet! (lesen Sie "en Fakultät").

Im vorherigen Fall stimmten die Anzahl der möglichen Elemente und die Anzahl der Stellen in der Reihe überein, und ihre Anzahl war gleich N. Es ist jedoch eine Situation möglich, in der es weniger Stellen in der Reihe als mögliche Elemente gibt. Mit anderen Worten, die Anzahl der Elemente in der Stichprobe ist gleich einer Zahl M und M< N. В этом случае задача определения количества возможных комбинаций может иметь два различных варианта.
Zunächst kann es erforderlich sein, die Gesamtsumme zu zählen mögliche Wege, die in einer Reihe von M Elementen aus N angeordnet werden können. Solche Verfahren werden Platzierungen genannt.
Zweitens könnte den Forscher interessieren, auf wie viele Arten M Elemente aus N ausgewählt werden können. In diesem Fall spielt die Reihenfolge der Elemente keine Rolle mehr, 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 finden, kann man auf die gleiche Argumentation zurückgreifen wie im Fall von Permutationen. An erster Stelle kann es noch N Elemente geben, an zweiter Stelle (N - 1) und so weiter. Aber für den letzten Platz, die Nummer Optionen ist nicht 1, sondern (N - M + 1), denn wenn die Zuordnung abgeschlossen ist, gibt es immer noch (N - M) unbenutzte Elemente.
Somit ist die Anzahl der Platzierungen über M Elementen von N gleich dem Produkt aller ganzen Zahlen von (N - M + 1) bis N oder äquivalent dem Quotienten N!/(N - M)!.

Offensichtlich ist die Anzahl der Kombinationen von M Elementen aus N kleiner als die Anzahl der Platzierungen. Für jede mögliche Kombination gibt es ein M! mögliche Platzierungen in Abhängigkeit von der Reihenfolge der Elemente dieser Kombination. Um diese Zahl zu finden, müssen Sie daher die Anzahl der Platzierungen über M Elemente von N durch N! teilen. Mit anderen Worten, die Anzahl der Kombinationen von M Elementen aus N ist N!/(M!*(N – M)!).