Kombinatorik
Kapitoly: Kombinatorik, Variationen, Permutation, Kombination, Variationen mit Wiederholungen, Kombination mit Wiederholung, Wie viele verschiedene PINs gibt es, Taschenrechner.
Willst du wissen, wie viele verschiedene Fünfer du aus einem Kartenspiel mit 32 Karten auswählen kannst? Das ist genau die Art von Problem, das die Kombinatorik löst. Es gibt zwei grundlegende kombinatorische Regeln - Summe und Produkt. Alle anderen Verfahren sind lediglich Erweiterungen dieser Grundprinzipien.
Die kombinatorische Regel der Summe
Die Summenregel ist sehr einfach - sie besagt, dass bei Mengen A, B, die kein gemeinsames Element haben, die Anzahl aller Möglichkeiten, ein Element aus der Vereinigung A ∪ B auszuwählen, gleich |A| + |B| ist, d. h. die Summe der Größen der Mengen.
Beginnen wir mit einem einfachen Beispiel. Wir haben 6 rote Bälle und 8 blaue Bälle. Werfen wir diese Kugeln in einen einzigen Pool. Wie viele Möglichkeiten haben wir insgesamt, wenn wir eine Kugel ziehen? Am Anfang hatten wir eine Menge roter Kugeln, nennen wir sie A, dann eine Menge blauer Kugeln, nennen wir sie B. Diese Mengen sind disjunkt, d.h. sie haben keine gleiche Kugel. Wir wollen eine Kugel ziehen, also haben wir insgesamt |A| + |B| = 6 + 8 = 14 Möglichkeiten. Das war's.
Die kombinatorische Produktregel
Wir haben wieder zwei Mengen, Z und M. Die Menge Z enthält drei Frauen und die Menge M enthält vier Männer. Wir fragen nun, wie viele verschiedene Paare von muž—žena wir aus diesen Mengen bilden können. Wir versuchen, immer eine Frau zu nehmen und ihr einen Mann zuzuordnen. Wir zählen die Anzahl aller Paare wie folgt: Wir nehmen eine Frau, Kate, und weisen ihr der Reihe nach alle Männer zu. Damit haben wir 4 verschiedene Paare, weil wir ihr 4 verschiedene Männer zuordnen können. Das Gleiche machen wir mit den beiden anderen Frauen, auch sie bilden jeweils 4 weitere Paare. Und das war's, wir haben insgesamt 4 + 4 + 4 = 12 Paare.
Was haben wir eigentlich gemacht? Wir haben die Größe der beiden Sets multipliziert. Wir hatten 3 Damen und 4 Herren, also ist die Gesamtzahl der Paare 3 · 4 = 12. Daraus ergibt sich die kombinatorische Produktregel. Wenn wir also zwei beliebige Mengen haben, aus denen wir Paare bilden, dann multiplizieren wir einfach die Anzahl der Elemente der einen Menge mit der Anzahl der Elemente der anderen Menge.
Dass dies tatsächlich zutrifft, sehen Sie unten. Im Folgenden sind alle Möglichkeiten aufgeführt, wie wir 3 Frauen und 4 Männer zu Paaren zusammenstellen können. Jede Zeile stellt die Möglichkeiten für eine der Frauen und jede Spalte die Möglichkeiten für einen der Männer dar. Wir haben also drei Zeilen und vier Spalten, also insgesamt řádky · sloupce Möglichkeiten.
$$\begin{eqnarray} &&[Z_1, M_1], [Z_1, M_2], [Z_1, M_3], [Z_1, M_4], \\ &&[Z_2, M_1], [Z_2, M_2], [Z_2, M_3], [Z_2, M_4], \\ &&[Z_3, M_1], [Z_3, M_2], [Z_3, M_3], [Z_3, M_4] \end{eqnarray}$$
Beispiele gelöst
- Wie viele verschiedene zweistellige Zahlen gibt es? Wie sieht eine solche zweistellige Zahl aus? Eine der Ziffern steht an der ersten Stelle 1, …, 9, während die zweite Stelle eine zusätzliche Null haben kann: 0, …, 9 Wir haben also 9 Ziffern in der ersten Menge und 10 in der zweiten. Wir wenden die kombinatorische Produktregel an, um das Endergebnis zu erhalten: 9 · 10 = 90.
- Wie viele verschiedene dreistellige Zahlen gibt es, bei denen keine Ziffer zweimal vorkommen kann? Neun Ziffern können wieder an der ersten Stelle stehen, aber die Zahl darf nicht mit Null beginnen. An der zweiten Stelle können alle Ziffern stehen, einschließlich der Null, aber es kann keine Ziffer an der ersten Stelle vorkommen, also ziehen wir von der Anzahl der zehn möglichen Ziffern eine ab (wenn unsere dreistellige Zahl zum Beispiel nur mit vier beginnt, ist klar, dass die Vier an der zweiten Stelle nicht mehr vorkommen kann, weil sie in der ganzen Zahl zweimal vorkommen würde). Auch hier können alle Ziffern an der dritten Stelle stehen, aber die Ziffer, die an der ersten oder zweiten Stelle steht, kann dort nicht stehen. Der Grund ist wieder derselbe. Wenn die Ziffer 4 an der ersten Stelle und die Ziffer 7 an der zweiten Stelle steht, können wir eine Ziffer von {0, …, 9} ∖ {4, 7} an die dritte Stelle addieren. Jetzt multiplizieren wir einfach mit 9 · 9 · 8 = 648. Die Gesamtzahl der Kombinationen beträgt 648.
- Wir würfeln zweimal hintereinander. Wie viele verschiedene Ergebnisse können wir erhalten? Beim ersten Wurf können wir 6 verschiedene Würfelergebnisse erhalten. Beim zweiten Wurf ist die Gesamtzahl der Möglichkeiten 6 · 6 = 36.
- Würfeln Sie zweimal hintereinander. Wie viele verschiedene Ergebnisse können wir erhalten, wenn wir beim ersten Wurf eine gerade Zahl würfeln? Beim ersten Wurf wurde eine gerade Zahl gewürfelt, d. h. es wurde eine der Zahlen 2, 4, 6 gewürfelt, so dass es insgesamt 3 Möglichkeiten gibt. Beim zweiten Wurf kann eine beliebige Zahl gewürfelt werden, so dass wir insgesamt 3 · 6 = 18 Möglichkeiten haben.