Wie viele Kombinationen 2 von 10. Kombinatorik: Grundregeln und Formeln. Permutationen und Wahrscheinlichkeitstheorie

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 notwendig sein, die Gesamtzahl der Möglichkeiten zu zählen, auf denen M Elemente aus N aneinandergereiht werden können.Solche Wege 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 ist die Anzahl der möglichen Optionen nicht eins, sondern (N - M + 1), denn wenn die Platzierung abgeschlossen ist, gibt es immer noch (N - M) ungenutzte 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)!).

KOMBINATORIK

Die Kombinatorik ist ein Zweig der Mathematik, der die Probleme der Auswahl und Anordnung von Elementen aus einer Grundmenge gemäß vorgegebenen Regeln untersucht. Formeln und Prinzipien der Kombinatorik werden in der Wahrscheinlichkeitstheorie verwendet, um die Wahrscheinlichkeit von Zufallsereignissen zu berechnen und dementsprechend die Verteilungsgesetze von Zufallsvariablen zu erhalten. Dies wiederum ermöglicht es, die Gesetzmäßigkeiten massenhafter Zufallsphänomene zu untersuchen, was für ein korrektes Verständnis der statistischen Gesetzmäßigkeiten, die sich in Natur und Technik 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 jede 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 eine Begleitperson bestellt werden?

Lösung

Sie können entweder einen Jungen oder ein Mädchen zum Dienst ernennen, d.h. Jeder der 16 Jungen oder jedes der 10 Mädchen kann im Dienst sein.

Gemäß der Summenregel erhalten wir, dass ein diensthabender Offizier 16+10=26 Möglichkeiten zugewiesen werden kann.

Produktregel. Es sei erforderlich, nacheinander k Aktionen auszuführen. 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, dann können alle k Aktionen zusammen sein durchgeführt:

Wege.

Beispiel 2

In der Klasse sind 16 Jungen und 10 Mädchen. Auf wie viele Arten können zwei Begleitpersonen bestellt werden?

Lösung

Die erste Person im Dienst kann entweder ein Junge oder ein Mädchen sein. Weil sind 16 Jungen und 10 Mädchen in der Klasse, dann kann man den ersten Diensthabenden auf 16 + 10 = 26 Arten ernennen.

Nachdem wir den ersten diensthabenden Offizier ausgewählt haben, können wir den zweiten aus den verbleibenden 25 Personen 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

Das klassische Problem der Kombinatorik ist das Problem der Zahl 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 der 10 verschiedenen Bücher auswählen, die als Geschenk erhältlich sind. Auf wie viele Arten kann dies geschehen?

Lösung

Wir müssen 4 von 10 Büchern auswählen, und die Reihenfolge der Auswahl spielt keine Rolle. Sie müssen also die Anzahl der Kombinationen von 10 Elementen mal 4 finden:

.

Betrachten Sie das Problem der Anzahl von Kombinationen mit Wiederholungen: Es gibt r identische Objekte von jedem von n verschiedenen Typen; wie viele Wege Kann wählen m() von diese (n*r) Artikel?

.

Beispiel 4

Die Konditorei verkaufte 4 Arten von Kuchen: Napoleons, Eclairs, Shortbread und Blätterteig. Auf wie viele Arten kann man 7 Kuchen kaufen?

Lösung

Weil Unter 7 Kuchen kann es Kuchen der gleichen Sorte geben, dann wird die Anzahl der Möglichkeiten, wie 7 Kuchen gekauft werden können, durch die Anzahl der Kombinationen mit Wiederholungen von 7 bis 4 bestimmt.

.

Platzierungen ohne Wiederholung. Platzierungen mit Wiederholungen

Das klassische 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 Ort Von bin anders setzt komme aus n anders Artikel?

Beispiel 5

Einige Zeitungen haben 12 Seiten. Es ist notwendig, vier Fotos auf den Seiten dieser Zeitung zu platzieren. Auf wie viele Arten kann dies geschehen, wenn keine Seite der Zeitung mehr als ein Foto enthalten soll?

Lösung.

Bei diesem Problem 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. Damit reduziert sich das Problem auf das klassische Problem, die Anzahl der Platzierungen ohne Wiederholungen aus 12 Elementen mal 4 Elementen zu bestimmen:

Somit können 4 Fotos auf 12 Seiten auf 11880 Arten angeordnet werden.

Auch die klassische Aufgabe der Kombinatorik ist das Problem der Anzahl von Platzierungen mit Wiederholungen, deren Inhalt durch die Frage ausgedrückt werden kann: wie viele Wege Kann DuBArmee Und Ort Von bin anders setzt komme aus n ArtikelMitredi welche Es gibt das gleiche?

Beispiel 6

Der Junge hatte Stempel mit den Nummern 1, 3 und 7 aus dem Brettspielset und beschloss, mit diesen Stempeln alle Bücher mit fünfstelligen Nummern zu versehen - um einen Katalog zusammenzustellen. Wie viele verschiedene fünfstellige Zahlen kann der Junge bilden?

Permutationen ohne Wiederholung. Permutationen mit Wiederholungen

Das klassische Problem der Kombinatorik ist das Problem der Anzahl von Permutationen ohne Wiederholung, dessen Inhalt durch die Frage ausgedrückt werden kann: wie viele Wege Kann Ort N verschieden Artikel An n anders setzt?

Beispiel 7

Wie viele aus vier Buchstaben bestehende „Wörter“ können aus den Buchstaben des Wortes „Ehe“ gebildet werden?

Lösung

Der allgemeine Satz besteht aus 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 gleiche gibt (Auswahl mit Return), lässt sich das Problem der Anzahl der Permutationen mit Wiederholungen durch die Frage ausdrücken: Auf wie viele Arten können n Objekte an n verschiedenen Orten neu angeordnet werden, wenn es unter n Objekten k verschiedene Arten 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“, insgesamt 9 Buchstaben. Daher ist die Anzahl der Permutationen mit Wiederholungen

HINTERGRUND ZUSAMMENFASSUNG ZUM ABSCHNITT "KOMBINATORIK"

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. Verzeihung.

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 Zahlen, die mir unbekannt sind, und ich glaube, dass sich darunter möglicherweise befinden 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 Thrash, der mir das versicherte es gab vierhundert Kombinationen, 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 viele 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, ein Programmierer, Künstler und Erfinder, schlug ganz richtig die richtige Lösung für das Problem vor und bescherte mir ein paar Minuten bester Laune: " 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 überprü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. Dennoch finden sich unter den Ausgangsdaten sowohl einfache Kombinationen als auch 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 iPhone-Bildschirmsperrprogramm (die Datenbank wurde vom Anwendungsentwickler Daniel Amitay bereitgestellt). . Die auf diesen Daten basierenden Grafiken 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.

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:

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 ermöglichen es, die grundsätzlich mögliche Anzahl unterschiedlicher Szenarien für die Entwicklung von Ereignissen zu berechnen.

Grundformel der Kombinatorik

Es gebe k Gruppen von Elementen, und die i-te Gruppe bestehe 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?
Weil eine gerade Zahl an dritter Stelle kann 0, 2, 4, 6 sein, also vier Stellen. Die zweite Stelle kann eine der sieben Ziffern sein. Die erste Stelle kann jede 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 lauten?
Die erste Stelle kann eine beliebige Zahl außer 0 sein, d.h. 9 Möglichkeiten. Die zweite Stelle kann eine beliebige Zahl sein, d.h. 10 Möglichkeiten. Die dritte Stelle kann auch eine beliebige Zahl sein, d.h. 10 Möglichkeiten. Die vierte und fünfte Ziffer sind vorgegeben, sie stimmen mit der ersten und zweiten überein, daher beträgt die Anzahl solcher Zahlen 9 * 10 * 10 = 900.
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?

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?
In den ersten Umschlag kannst du einen der acht Buchstaben stecken, in den zweiten einen der sieben restlichen Buchstaben, in den dritten einen der sechs usw. n = 8! = 1*2*3*4*5*6*7*8 = 40320.
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?