Kombinatorik

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\} \]

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.