Das Wichtigste in Kürze

In der Kombinatorik gibt es vier mögliche Aufgabentypen:

Ist die Reihenfolge wichtig, benutzen wir die k-Permutationen (Variationen):

\[ ^nP_k = \frac{n!}{(n-k)!} \qquad \qquad \overline{^nP_k}=n^k \]

Ein Spezialfall der k-Permutationen sind die Permutationen. Der Unterschied liegt darin, dass bei Permutationen alle Objekte permutiert werden, d.h. $k=n$, während bei k-Permutationen nur eine kleinere Auswahl permutiert wird ($k<n$).

Wenn wir Problemstellungen haben ohne Reihenfolge, benutzen wir die Kombinationen:

\[ ^nC_k = \begin{pmatrix} n \\ k \end{pmatrix} \qquad \qquad \overline{^nC_k} = \begin{pmatrix} k+n-1 \\ k \end{pmatrix} \]

Dabei wird der Fall mit Wiederholung jeweils mit einem Querstrich markiert. Die Klammerausdrücke sind sog. Binomialkoeffizienten.

Wenn wir mehrstufige Probleme haben, stellen wir uns einen Ereignisbaum vor, aus welchem die Anzahl Äste gemäss Fundamentalprinzip der Kombinatorik miteinander multipliziert werden muss, z.B. für die Bildung von 6er-Teams aus 18 Schülerinnen und Schüler:

\[ ^{18}C_6 \cdot ^{12}C_6 \cdot ^{6}C_6 \]

Hack

Merke Dir die folgende Tabelle mit den Beispielen und versuche die neue Kombinatorik-Fragestellung einem dieser vier Fälle zuzuordnen. Von da weg, musst du nur noch die passende Formel nehmen und die richtigen Zahlen einsetzen.

mit Reihenfolge
k-Permutationen (Variationen)
ohne Reihenfolge
Kombinationen
ohne Zurücklegen (ohne Wiederholung)Bsp: Podest
\[ ^nP_k \]
Bsp: Lotto
\[ ^nC_k \]
mit Zurücklegen (mit Wiederholung)Bsp: Code
\[ \overline{^nP_k} \]
Bsp: Eiskugeln
\[ \overline{^nC_k} \]

Videos

Im ersten Video kriegst du einen einleitenden Überblick.
Das zweite Video fasst die verschiedenen Methoden zusammen.

Um die beiden Video anzusehen, musst du einloggen
Noch kein Login? Hier registrieren

Der “Code” ist streng genommen eine k-Permutation (Variation) und keine “Kombination”!

Aufgaben in der Kombinatorik sind meistens Textaufgaben. Hier ist es wichtig zu wissen, dass es eigentlich nur vier Möglichkeiten gibt, mit vier Formeln. Wir werden hier nicht die einzelnen Fälle diskutieren, sondern sie nur kurz vorstellen.

Um den richtigen Fall unter den vier Möglichkeiten herauszufinden, stellen wir zwei Fragen:

  • Ist es ein Problem mit oder ohne Reihenfolge?
  • Sind Wiederholungen möglich oder nicht?

Die erste Frage kann relativ einfach beantwortet werden: Kann ich die Reihenfolge einfach vertauschen? Gibt es überhaupt eine Reihenfolge?

Wenn ich unter 20 Eissorten 3 Eiskugeln auslesen darf, spielt die Reihenfolge keine Rolle. Auch kommt es beim Lotto nicht darauf an, in welcher Reihenfolge die Gewinnerzahlen gezogen worden sind.

Wenn ein Rennen noch läuft, gibt es verschiedene, denkbare Besetzungen für das Podest. Hier kann ich die Namen auf dem Podest nicht einfach vertauschen, denn die Reihenfolge (1. Platz, 2. Platz, 3. Platz) ist relevant. Ebenso ist Reihenfolge der Buchstaben und Zahlen bei einem Passwort oder Code entscheidend. Ich kann nicht einfach die gleichen Zahlen in einer anderen Reihenfolge eingeben.

Die zweite Frage untersucht, ob Wiederholungen möglich sind.

Bei den 3 Eiskugeln ist das Wählen von z.B. zwei Schokoladekugeln möglich – warum nicht? Beim Lotto kommt die gleiche Zahl aber nicht mehrmals vor. Hier ist die Wiederholung ausgeschlossen.

Ebenso kann es nicht sein, dass die gleiche Person auf mehreren Plätzen auf dem Podest steht – es gibt keine Wiederholung. Beim Code kann ich aber die gleiche Zahl oder den gleichen Buchstaben mehrmals verwenden.

Wir erhalten so die vier verschiedenen Fälle:

mit Reihenfolge
k-Permutationen (Variationen)
ohne Reihenfolge
Kombinationen
ohne Zurücklegen (ohne Wiederholung)Bsp: Podest
\[ ^nP_k \]
Bsp: Lotto
\[ ^nC_k \]
mit Zurücklegen (mit Wiederholung)Bsp: Code
\[ \overline{^nP_k} \]
Bsp: Eiskugeln
\[ \overline{^nC_k} \]

Wenn wir die Terminologie des Urnenmodells verwenden, reden wir bei der Wiederholung von “mit Zurücklegen”. Wir meinen damit, dass die gezogene Kugel zurückgelegt wird und deshalb nochmals gezogen werden kann.

Die linke Spalte “mit Reihenfolge” steht für die sog. k-Permutationen, die oft auch Variationen genannt werden. Die rechte Spalte “ohne Reihenfolge” enthält die sog. Kombinationen.

Beachte, dass der “Code” streng genommen eine k-Permutation darstellt und nicht eine “Kombination”, wie das üblicherweise genannt wird.

Mit Reihenfolge: k-Permutationen (Variationen) und Permutationen

Wenn die Reihenfolge eine Rolle spielt, können wir sie nicht einfach vertauschen, ohne etwas anderes zu kriegen. Wir haben dann sog. k-Permutationen (Variationen).

Nachfolgend sind zwei Beispiele in der Form von sog. n-Tupeln geschrieben, d.h. mit Klammern und Kommas, die die einzelnen Objekte trennt:

\[ (N,\; A,\; M,\; E) \;\;\neq\;\; (A,\; M,\; E,\; N) \]

\[ (\text{Meier}, \text{Huber}, \text{Schmid}) \;\;\neq\;\; (\text{Schmid}, \text{Meier}, \text{Huber}) \]

Wenn wir aus einer (grösseren) Grundmenge eine (kleinere) Teilmenge von Objekten wählen, haben wir sog. k-Permutationen (Variationen).

Die Besetzungsmöglichkeiten für ein Siegerpodest erlaubt keine Wiederholungen. Wir haben nur 3 Plätze für z.B. 20 Athleten: “3 aus 20”

\[ ^{20}P_3 \]

Wenn wir Wiederholungen zulassen, schreiben wir einen Querstrich, z.B. ist ein Zahlencode von 4 Ziffern eine Auswahl von “4 aus 10”, weil es 10 Ziffern gibt (0, 1, 2, … bis 9):

\[ \overline{^{10}P_4} \]

Alle Objekte mit Reihenfolge: Permutation

Die Permutationen gehören zu den k-Permutationen (Variationen). Sie sind eine Untermenge davon.

Wenn wir nicht eine kleinere Auswahl aus einer grösseren Grundmenge haben, sondern die ganze Grundmenge verwenden, sprechen wir von einer (einfachen) Permutation:

So können die 4 Buchstaben in “NAME” auf 24 verschiedene Arten aufgeschrieben werden, denn die Anzahl möglicher Permutationen von 4 Objekten ist:

\[ ^4P = 4! = 24 \]

Eigentlich handelt es sich hier um die k-Permutation “4 aus 4”:

\[ ^4P = ^4P_4 \]

Ohne Reihenfolge: Kombinationen

Bei Problemstellungen ohne Reihenfolge, betrachten wir die Sache wie eine mathematische Menge von Objekten. Wir benutzen in diesem Fall die sog. Kombinationen.

Wenn wir bei einem Rennen mit 20 Athleten nicht ein Podest mit 1. Platz, 2. Platz und 3. Platz haben, sondern die ersten drei Plätze qualifizieren sich für die nationalen Meisterschaften, dann ist die Reihenfolge nicht mehr relevant.

Die drei Ersten kommen in den gleichen Topf der Qualifizierten und einzelne Permutationen der drei werden nicht einzeln gezählt, sondern gehören zur gleichen und einzigen Kombination ohne Reihenfolge:

\[ (\text{Meier}, \text{Huber}, \text{Schmid}), \;\; (\text{Schmid}, \text{Meier}, \text{Huber}) \quad \rightarrow \quad \Big\{\text{Meier}, \text{Huber}, \text{Schmid} \Big\} \]

Die Problemstellung ist jetzt, wie viele Kombinationen “3 aus 20” gibt es:

\[ ^{20}C_3 \]

Ist die Wiederholung erlaubt, wie im Beispiele der Eiskugeln, kann eine mögliche Kombination von 3 Eiskugeln aus einer Auswahl von 20 Eissorten, also “3 aus 20” sein:

\[ \overline{^{20}C_3} \]

Die Wiederholung (Querstrich) besteht z.B. darin, dass jemand zwei Mal die gleiche Eissorte wählt. Eine mögliche Kombination könnte deshalb sein:

\[ \big\{ \text{Schokolade}, \;\text{Schokolade}, \;\text{Vanille} \big\} \]

Beispiel: Volleyball-Turnier

Für ein Volleyball-Turnier sollen alle 360 Schülerinnen und Schüler einer Schule in 6er-Teams eingeteilt werden. Um welche Art von Kombinatorik-Aufgabe handelt es sich?

Wie ändert sich die Sache, wenn nur die Körpergrösse auf Zentimeter gerundet, eine Rolle spielt?

Im ersten Fall handelt es sich um einen Fall von “6 aus 360”, wobei Reihenfolge keine Rolle spielt und Wiederholungen ausgeschlossen sind.

Wir haben keine Reihenfolge, weil es nicht darauf ankommt, in welcher Reihenfolge die Schülerinnen und Schüler eingeteilt werden. Sie sind gewissermassen “Elemente einer Menge” und innerhalb des Teams gibt es keine Reihenfolge.

Wir haben auch keine Wiederholungen, denn jeder Schüler, jede Schülerin ja nur einmal vorkommt.

Es handelt sich demnach um eine Kombination ohne Wiederholung, für das erste Team gilt: “6 aus 360”:

\[ ^{360}C_6 \]

Wenn wir die Körpergrössen nehmen, statt die Personen, sind die Wiederholungen möglich. Es ist immer noch ein “6 aus 360”-Problem, aber mit Wiederholung:

\[ \overline{^{360}C_6} \]

Fundamentalprinzip der Kombinatorik

Wenn wir mehrstufige Probleme haben, bilden wir am besten einen Ereignisbaum.

Beispiel: Sarah hat zur Auswahl: 8 Hosen, 2 Sockenfarben und 4 verschiedene Blusen. Auf wie viele Möglichkeiten kann sie sich anziehen?

Für die Wahl der Hose gibt es 8 mögliche Pfade. Für die Wahl der Sockenfarbe deren zwei und schliesslich je 4 Pfade für die Blusen. Wir zeichnen den Baum und statt die Äste zu zählen, multiplizieren wir (siehe unten links):

Beachte, dass wenn das Ergebnis eines Vorgangs die Anzahl darauf folgender Möglichkeiten unterschiedlich beeinflusst, d.h. die Anzahl Verzweigungen vom Pfad abhängt, entsteht ein unregelmässiger Baum. Die Anzahl Enden erhalten wir in diesem Fall durch Addition (siehe oben rechts).

Die Verknüpfung von mehrstufigen Problemen durch Multiplikation wird Fundamentalprinzip der Kombinatorik genannt: Wenn mehrere Vorgänge mit je einer gewissen Anzahl Möglichkeiten (Anzahl Verzweigungen im Baumdiagramm) nacheinander stattfinden, erhalten wir die Anzahl Enden mit der Multiplikation aller Verzweigungen.

Beispiel: Volleyball-Turnier

Wie viele Möglichkeiten gibt es, die besten 18 Schülerinnen und Schüler der Schule in 6er-Teams einzuteilen?

Für das erste Team haben wir eine Kombination von “6 aus 18”:

\[ ^{18}C_6 = \begin{pmatrix} 18 \\ 6 \end{pmatrix} = 18’564 \]

Für das zweite Team haben wir noch 12 Schülerinnen und Schüler zur Auswahl, deshalb haben wir jetzt “6 aus 12”:

\[ ^{12}C_6 = \begin{pmatrix} 12 \\ 6 \end{pmatrix} = 924 \]

Schliesslich würde für das dritte Team gelten:

\[ ^{6}C_6 = \begin{pmatrix} 6 \\ 6 \end{pmatrix} = 1 \]

Dass wir hier nur 1 kriegen ist logisch, denn das Team kann gar nicht mehr zusammengestellt werden, es besteht ja schon durch die restlichen 6 Schülerinnen und Schüler.

Diese dreistufige Problemstellung wird jetzt berechnet, indem wir uns einen Baum vorstellen mit 18’564 ersten Ästen und 924 zweiten Ästen. Die dritte Stufe fällt weg, denn das ist das dritte Team, für welches wir keine Verzweigung mehr haben.

Die Anzahl Möglichkeiten erhalten wir durch die Multiplikation gemäss Fundamentalprinzip der Kombinatorik:

\[ ^{18}C_6 \cdot ^{12}C_6 = 18’564 \cdot 924 = \underline{17’153’136} \]

Ist doch eine erstaunlich grosse Zahl für gerade mal 18 Schülerinnen und Schüler!

Aufgabensammlung

Permutationen (5052)

6 Aufgaben, 20 Teilaufgaben mit Lösungen (pdf/Video):

  • Einfache bis anspruchsvollere Anwendungen von Permutationen, mit und ohne Wiederholungen
  • k-Permutationen mit oder ohne Zurücklegen (Wiederholung)

Um auf die Übung zugreifen zu können, musst du einloggen
Noch kein Login? Hier registrieren

Binomialkoeffizient und Kombinationen (5053)

7 Aufgaben, 25 Teilaufgaben mit Lösungen (pdf/Video):

  • Berechnen von Binomialkoeffizienten
  • Beziehungen zwischen verschiednene Binomialkoeffizienten
  • Textaufgaben zu Kombinationen, mit und ohne Wiederholung

Um auf die Übung zugreifen zu können, musst du einloggen
Noch kein Login? Hier registrieren

Lernziele

  • Du kennst für die Kurzschreibweise für die Permutationen, k-Permutationen (Variationen) und für Kombinationen
  • Du weisst, wie du eine Fragestellung auf eine der vier Möglichkeiten in der Kombinatorik beschränken kannst.

Mini-Test

(zu diesem Thema gibt es noch keinen Mini-Test)

Weitere Links


Physik- und Mathe-Hacks lernen…

…im Hacker-Club!