Dieser Artikel konzentriert sich auf einen speziellen Bereich der Mathematik namens Kombinatorik. Formeln, Regeln, Beispiele zur Problemlösung - all das finden Sie hier, indem Sie den Artikel bis zum Ende lesen.
Also, was ist dieser Abschnitt? Die Kombinatorik befasst sich mit der Frage des Zählens beliebiger Objekte. Aber in diesem Fall sind die Objekte keine Pflaumen, Birnen oder Äpfel, sondern etwas anderes. Kombinatorik hilft uns, die Wahrscheinlichkeit eines Ereignisses zu finden. Wie groß ist zum Beispiel beim Kartenspielen die Wahrscheinlichkeit, dass der Gegner eine Trumpfkarte hat? Oder ein solches Beispiel - wie groß ist die Wahrscheinlichkeit, dass Sie aus einer Tüte mit zwanzig Knäueln genau weiß bekommen? Für diese Art von Aufgaben müssen wir zumindest die Grundlagen dieses Abschnitts der Mathematik kennen.
Kombinatorische Konfigurationen
In Anbetracht der Frage nach den grundlegenden Konzepten und Formeln der Kombinatorik müssen wir uns unbedingt mit kombinatorischen Konfigurationen befassen. Sie werden nicht nur zur Formulierung, sondern auch zur Lösung verschiedener kombinatorischer Probleme verwendet. Beispiele für solche Modelle sind:
- Platzierung;
- Permutation;
- Kombination;
- Zahlenzusammensetzung;
- geteilte Zahl.
Wir werden später ausführlicher auf die ersten drei eingehen, aber wir werden uns in diesem Abschnitt mit der Zusammensetzung und Aufteilung befassen. Wenn sie von der Zusammensetzung einer bestimmten Zahl (z. B. a) sprechen, meinen sie die Darstellung der Zahl a als geordnete Summe einiger positiver Zahlen. Und ein Split ist eine unsortierte Summe.
Abschnitte
Bevor wir direkt auf die Formeln der Kombinatorik und die Problembetrachtung eingehen, lohnt es sich, darauf zu achten, dass die Kombinatorik, wie auch andere Bereiche der Mathematik, eigene Unterbereiche hat. Dazu gehören:
- Aufzählung;
- strukturell;
- extrem;
- Ramsey-Theorie;
- probabilistisch;
- topologisch;
- unendlich.
Im ersten Fall sprechen wir von enumerativer Kombinatorik, die Probleme betrachten das Aufzählen oder Zählen verschiedener Konfigurationen, die durch Elemente von Mengen gebildet werden. In der Regel werden diesen Mengen einige Einschränkungen auferlegt (Unterscheidbarkeit, Ununterscheidbarkeit, Wiederholungsmöglichkeit usw.). Und die Anzahl dieser Konfigurationen wird nach der Additions- oder Multiplikationsregel berechnet, auf die wir später noch eingehen werden. Die Strukturkombinatorik umfasst die Theorien von Graphen und Matroiden. Ein Beispiel für ein extremalkombinatorisches Problem ist die größte Dimension eines Graphen, der die folgenden Eigenschaften erfüllt … Im vierten Absatz haben wir die Ramsey-Theorie erwähnt, die das Vorhandensein regelmäßiger Strukturen in zufälligen Konfigurationen untersucht. WahrscheinlichkeitKombinatorik ist in der Lage, die Frage zu beantworten - wie groß ist die Wahrscheinlichkeit, dass eine gegebene Menge eine bestimmte Eigenschaft hat. Wie Sie sich vorstellen können, wendet die topologische Kombinatorik Methoden der Topologie an. Und schließlich der siebte Punkt – die unendliche Kombinatorik untersucht die Anwendung kombinatorischer Methoden auf unendliche Mengen.
Additionsregel
Unter den Formeln der Kombinatorik findet man ganz einfache, die uns schon lange bekannt sind. Ein Beispiel ist die Summenregel. Angenommen, wir haben zwei Aktionen (C und E), wenn sie sich gegenseitig ausschließen, Aktion C kann auf verschiedene Arten ausgeführt werden (z. B. a) und Aktion E kann auf b-Methoden ausgeführt werden, dann kann jede von ihnen (C oder E) kann auf a + b Weise gemacht werden.
Theoretisch ist das ziemlich schwer zu verstehen, wir werden versuchen, den ganzen Punkt mit einem einfachen Beispiel zu vermitteln. Nehmen wir die durchschnittliche Anzahl von Schülern in einer Klasse - sagen wir, es sind fünfundzwanzig. Darunter sind fünfzehn Mädchen und zehn Jungen. Täglich wird der Klasse eine Begleitperson zugeteilt. Wie viele Möglichkeiten gibt es heute, einen Klassenwärter zuzuweisen? Die Lösung des Problems ist ganz einfach, wir greifen auf die Additionsregel zurück. Der Text der Aufgabe besagt nicht, dass nur Jungen oder nur Mädchen im Dienst sein können. Daher könnte es eines der fünfzehn Mädchen oder einer der zehn Jungen sein. Wenn wir die Summenregel anwenden, erh alten wir ein ziemlich einfaches Beispiel, das ein Grundschüler leicht bewältigen kann: 15 + 10. Nach der Berechnung erh alten wir die Antwort: fünfundzwanzig. Das heißt, es gibt nur fünfundzwanzig WegeWeisen Sie eine Dienstklasse für heute zu.
Multiplikationsregel
Auch die Multiplikationsregel gehört zu den Grundformeln der Kombinatorik. Beginnen wir mit der Theorie. Angenommen, wir müssen mehrere Aktionen ausführen (a): Die erste Aktion wird auf 1-Weise ausgeführt, die zweite - auf 2-Wege, die dritte - auf 3-Wege und so weiter, bis die letzte a-Aktion auf sa-Weise ausgeführt wird. Dann können alle diese Aktionen (von denen wir insgesamt haben) auf N Arten ausgeführt werden. Wie berechnet man das unbekannte N? Die Formel hilft uns dabei: N \u003d c1c2c3…ca.
Auch hier ist theoretisch nichts klar, kommen wir zu einem einfachen Beispiel für die Anwendung der Multiplikationsregel. Nehmen wir dieselbe Klasse mit 25 Personen, in der 15 Mädchen und 10 Jungen lernen. Nur dieses Mal müssen wir zwei Begleiter auswählen. Sie können entweder nur Jungen oder Mädchen sein oder ein Junge mit einem Mädchen. Wir wenden uns der elementaren Lösung des Problems zu. Wir wählen den ersten Begleiter, wie wir im letzten Absatz entschieden haben, wir erh alten fünfundzwanzig mögliche Optionen. Die zweite diensthabende Person kann jede der verbleibenden Personen sein. Wir hatten fünfundzwanzig Schüler, wir haben einen ausgewählt, was bedeutet, dass jeder der verbleibenden vierundzwanzig Personen der zweite im Dienst sein kann. Schließlich wenden wir die Multiplikationsregel an und stellen fest, dass die beiden Begleiter auf sechshundert Arten gewählt werden können. Wir haben diese Zahl erh alten, indem wir fünfundzwanzig und vierundzwanzig multipliziert haben.
Tausch
Nun betrachten wir eine weitere Formel der Kombinatorik. In diesem Abschnitt des Artikels, wirReden wir über Permutationen. Betrachten Sie das Problem sofort anhand eines Beispiels. Nehmen wir Billardkugeln, wir haben die n-te Anzahl davon. Wir müssen berechnen: wie viele Möglichkeiten es gibt, sie in einer Reihe anzuordnen, also eine geordnete Menge zu bilden.
Fangen wir an, wenn wir keine Eier haben, dann haben wir auch keine Platzierungsmöglichkeiten. Und wenn wir einen Ball haben, dann ist die Anordnung auch gleich (mathematisch lässt sich das so schreiben: Р1=1). Zwei Kugeln können auf zwei verschiedene Arten angeordnet werden: 1, 2 und 2, 1. Daher ist Р2=2. Drei Kugeln können auf sechs Arten angeordnet werden (Р3=6): 1, 2, 3; 1, 3, 2; 2, 1, 3; 2, 3, 1; 3, 2, 1; 3, 1, 2. Und wenn es nicht drei solcher Kugeln sind, sondern zehn oder fünfzehn? Alle Möglichkeiten aufzuzählen ist sehr lang, dann kommt uns die Kombinatorik zu Hilfe. Die Permutationsformel hilft uns, die Antwort auf unsere Frage zu finden. Pn=nP(n-1). Wenn wir versuchen, die Formel zu vereinfachen, erh alten wir: Pn=n (n - 1) … 21. Und das ist das Produkt der ersten natürlichen Zahlen. Eine solche Zahl wird Fakultät genannt und mit n! bezeichnet.
Betrachten wir das Problem. Der Anführer baut jeden Morgen seine Abteilung in einer Linie (zwanzig Personen). Es gibt drei beste Freunde in der Abteilung - Kostya, Sasha und Lesha. Wie groß ist die Wahrscheinlichkeit, dass sie nebeneinander stehen? Um die Antwort auf die Frage zu finden, müssen Sie die Wahrscheinlichkeit eines „guten“Ergebnisses durch die Gesamtzahl der Ergebnisse teilen. Die Gesamtzahl der Permutationen beträgt 20!=2,5 Trillionen. Wie kann man die Anzahl der "guten" Ergebnisse zählen? Angenommen, Kostya, Sasha und Lesha sind ein Übermensch. Dann wirWir haben nur achtzehn Fächer. Die Anzahl der Permutationen beträgt in diesem Fall 18=6,5 Billiarden. Bei all dem können sich Kostya, Sasha und Lesha in ihrem unteilbaren Triple beliebig untereinander bewegen, und das sind 3 mehr!=6 Optionen. Wir haben also insgesamt 18 „gute“Konstellationen!3! Wir müssen nur die gewünschte Wahrscheinlichkeit finden: (18!3!) / 20! Das sind ungefähr 0,016. Wenn man es in Prozent umrechnet, sind es nur 1,6 %.
Unterkunft
Nun betrachten wir eine weitere sehr wichtige und notwendige Kombinatorik-Formel. Die Unterkunft ist unser nächstes Thema, das wir Ihnen in diesem Abschnitt des Artikels empfehlen. Wir werden komplizierter. Nehmen wir an, wir wollen mögliche Permutationen betrachten, nur nicht von der ganzen Menge (n), sondern von einer kleineren (m). Das heißt, wir betrachten Permutationen von n Elementen durch m.
Die Grundformeln der Kombinatorik sollten nicht nur auswendig gelernt, sondern verstanden werden. Auch wenn sie komplizierter werden, da wir nicht einen Parameter haben, sondern zwei. Angenommen, m \u003d 1, dann A \u003d 1, m \u003d 2, dann A \u003d n(n - 1). Wenn wir die Formel weiter vereinfachen und zur Notation mit Fakultäten wechseln, erh alten wir eine recht knappe Formel: A \u003d n! / (n - m)!
Kombination
Wir haben fast alle Grundformeln der Kombinatorik mit Beispielen betrachtet. Kommen wir nun zum letzten Schritt der Betrachtung des Grundkurses der Kombinatorik - dem Kennenlernen der Kombination. Jetzt werden wir m Gegenstände aus den n auswählen, die wir haben, während wir sie alle auf alle möglichen Arten auswählen werden. Wie unterscheidet sich das dann von der Unterkunft? Wir werden nichtOrdnung beachten. Dieser ungeordnete Satz wird eine Kombination sein.
Führe sofort die Notation ein: C. Wir nehmen Platzierungen von m Kugeln aus n heraus. Wir achten nicht mehr auf die Reihenfolge und erh alten wiederholte Kombinationen. Um die Anzahl der Kombinationen zu erh alten, müssen wir die Anzahl der Platzierungen durch m teilen! (m Fakultät). Das heißt, C \u003d A / m! Somit gibt es ein paar Möglichkeiten, aus n Bällen ungefähr gleich viele auszuwählen, wie viele, um fast alles zu wählen. Dafür gibt es einen logischen Ausdruck: Wenig zu wählen ist gleichbedeutend damit, fast alles wegzuwerfen. Wichtig ist an dieser Stelle auch zu erwähnen, dass die maximale Anzahl an Kombinationen erreicht werden kann, wenn man versucht, die Hälfte der Items auszuwählen.
Wie wählt man eine Formel zur Lösung eines Problems?
Wir haben die Grundformeln der Kombinatorik im Detail untersucht: Platzierung, Permutation und Kombination. Unsere Aufgabe ist es nun, die Wahl der notwendigen Formel zur Lösung des Problems in der Kombinatorik zu erleichtern. Sie können das folgende ziemlich einfache Schema verwenden:
- Fragen Sie sich: Wird die Reihenfolge der Elemente im Aufgabentext berücksichtigt?
- Wenn die Antwort nein ist, dann verwende die Kombinationsformel (C=n! / (m!(n - m)!)).
- Wenn die Antwort nein ist, müssen Sie noch eine weitere Frage beantworten: Sind alle Elemente in der Kombination enth alten?
- Wenn ja, dann verwende die Permutationsformel (P=n!).
- Wenn die Antwort nein ist, dann verwenden Sie die Zuordnungsformel (A=n! / (n - m)!).
Beispiel
Wir haben die Elemente der Kombinatorik, Formeln und einige andere Themen berücksichtigt. Kommen wir nun zuin Anbetracht eines echten Problems. Stellen Sie sich vor, Sie haben eine Kiwi, eine Orange und eine Banane vor sich.
Frage eins: Auf wie viele Arten können sie neu angeordnet werden? Dazu verwenden wir die Permutationsformel: P=3!=6 Wege.
Frage zwei: Auf wie viele Arten kann eine Frucht ausgewählt werden? Das ist offensichtlich, wir haben nur drei Möglichkeiten - wählen Sie Kiwi, Orange oder Banane, aber wir wenden die Kombinationsformel an: C \u003d 3! / (2!1!)=3.
Frage drei: Auf wie viele Arten können zwei Früchte ausgewählt werden? Welche Möglichkeiten haben wir? Kiwi und Orange; Kiwi und Banane; Orange und Banane. Das heißt, drei Optionen, aber dies lässt sich leicht mit der Kombinationsformel überprüfen: C \u003d 3! / (1!2!)=3
Frage vier: Auf wie viele Arten kann man drei Früchte auswählen? Wie Sie sehen, gibt es nur eine Möglichkeit, drei Früchte auszuwählen: Nehmen Sie eine Kiwi, eine Orange und eine Banane. C=3! / (0!3!)=1.
Frage fünf: Auf wie viele Arten kannst du mindestens eine Frucht auswählen? Diese Bedingung impliziert, dass wir eine, zwei oder alle drei Früchte nehmen können. Daher addieren wir C1 + C2 + C3=3 + 3 + 1=7. Das heißt, wir haben sieben Möglichkeiten, mindestens ein Stück Obst vom Tisch zu nehmen.
