Permutationen und Kombinatorik: Grundlagen für Olympiaden

Wer sich ernsthaft auf eine Mathematik-Olympiade vorbereitet, kommt an der Kombinatorik nicht vorbei. Kaum ein anderes Gebiet der Mathematik erzeugt so elegante Aufgaben bei gleichzeitig so klarer innerer Logik – vorausgesetzt, man hat die grundlegenden Konzepte wirklich durchdrungen. Permutationen sind dabei das Herzstück, der Ausgangspunkt für eine ganze Familie von Zählmethoden.

Was sind Permutationen?

Eine Permutation ist eine Anordnung von Objekten in einer bestimmten Reihenfolge. Stellt man sich die Menge {1, 2, 3} vor, so gibt es genau sechs mögliche Anordnungen: 123, 132, 213, 231, 312, 321.

Die allgemeine Formel lautet:

P(n) = n!

wobei n! (gesprochen: n Fakultät) das Produkt aller natürlichen Zahlen von 1 bis n ist. Für n = 3 gilt demnach 3! = 1 · 2 · 3 = 6. Für n = 10 sind es bereits 3.628.800 Anordnungen.

Permutationen mit Wiederholung

Was passiert, wenn nicht alle Elemente verschieden sind? Nehmen wir das Wort ANNA: Es besteht aus 4 Buchstaben, aber A und N kommen je zweimal vor. Würde man einfach 4! rechnen, zählte man jede inhaltlich identische Anordnung mehrfach. Die korrekte Formel ist:

P(n; k₁, k₂, …) = n! / (k₁! · k₂! · … )

Für ANNA ergibt das: 4! / (2! · 2!) = 24 / 4 = 6 verschiedene Anordnungen.

Diese Art von Aufgabe taucht bei Olympiaden häufig in verkleideter Form auf – etwa als Gitterwegaufgabe, bei der man von einem Punkt A zu einem Punkt B auf einem Schachbrettgitter gelangen soll, ausschließlich nach rechts oder nach oben.

Kombinationen: Wenn die Reihenfolge egal ist

Neben der Permutation gibt es die Kombination. Hier fragt man nicht nach Anordnungen, sondern nach Auswahlen: Wie viele Möglichkeiten gibt es, aus n Objekten genau k herauszugreifen, ohne dass die Reihenfolge eine Rolle spielt?

C(n, k) = n! / (k! · (n − k)!)

Diesen Ausdruck kennt man auch als Binomialkoeffizient, geschrieben als "n über k". Er bildet das Fundament des Pascalschen Dreiecks und taucht in der Wahrscheinlichkeitsrechnung wie in der abzählenden Kombinatorik allgegenwärtig auf.

Variationen – die vergessene dritte Variante

Zwischen Permutation und Kombination steht die Variation: Man wählt k Objekte aus n aus und beachtet die Reihenfolge. Ohne Wiederholung gilt:

V(n, k) = n! / (n − k)!

Ein typisches Beispiel: Wie viele Möglichkeiten gibt es, drei Schüler aus einer Klasse von zwanzig auf die Plätze 1, 2 und 3 zu verteilen? V(20, 3) = 20 · 19 · 18 = 6840.

Olympiadeaufgaben: Typische Muster erkennen

Bei Wettbewerben – von der regionalen Mathematik-Olympiade bis zum Bundeswettbewerb Mathematik – erscheinen kombinatorische Aufgaben selten in Reinform. Stattdessen sind sie in Szenarien eingebettet, die man erst "übersetzen" muss.

Aufgabe: Das Handschlagproblem

Auf einer Konferenz treffen sich n Personen. Jede Person schüttelt genau einmal die Hand jeder anderen. Wie viele Händeschütteln gibt es insgesamt?

Die Antwort ist C(n, 2) = n(n − 1)/2. Man wählt 2 Personen aus n aus, Reihenfolge spielt keine Rolle. Für n = 10 Personen ergeben sich 45 Händeschütteln.

Aufgabe: Wege auf einem Gitter

Auf einem 4×4-Gitter bewegt man sich von der unteren linken Ecke zur oberen rechten Ecke, stets nur nach rechts oder nach oben. Wie viele Wege gibt es?

Man macht insgesamt 8 Schritte: 4 nach rechts (R) und 4 nach oben (O). Gesucht ist die Anzahl der Permutationen des Wortes RRRROOOO:

8! / (4! · 4!) = 70

Algorithmen zur Nummerierung von Permutationen

Eine bei Informatik-Olympiaden oft auftauchende Aufgabengattung verlangt nicht nur das Zählen, sondern auch das Nummerieren und Rekonstruieren von Permutationen in lexikographischer Reihenfolge. Hier kommt der sogenannte Lehmer-Code ins Spiel.

Die Idee: Man weist jeder Permutation eine eindeutige Nummer zu, indem man sie in einem fakultätsbasierten Zahlensystem (engl. factoradic) darstellt. Der Algorithmus funktioniert folgendermaßen:

1. Bestimme für jede Stelle, wie viele noch nicht verwendeten Elemente kleiner sind als das gewählte Element.
2. Die resultierende Folge von Koeffizienten (der Lehmer-Code) wird multipliziert mit den entsprechenden Fakultäten aufsummiert.

Beispiel: Die Permutation (3, 1, 4, 2) aus {1, 2, 3, 4}

• Position 0: 3 ist das drittkleinste von {1,2,3,4} → Koeffizient 2
• Position 1: 1 ist das kleinste von {1,2,4} → Koeffizient 0
• Position 2: 4 ist das größte von {2,4} → Koeffizient 1
• Position 3: 2 ist das einzige Element → Koeffizient 0

Nummer = 2·3! + 0·2! + 1·1! + 0·0! = 12 + 0 + 1 + 0 = 13

Die Umkehrrichtung – aus einer Nummer die entsprechende Permutation zu rekonstruieren – erfolgt durch sukzessive Division mit Rest. Beide Operationen laufen in O(n²) und bilden die Grundlage für zahlreiche Olympiadeaufgaben, bei denen man etwa die "k-te Permutation in lexikographischer Reihenfolge" bestimmen soll.

Klassische Fehlerquellen

Beim Einstieg in die Kombinatorik passieren immer wieder dieselben Fehler:

• Verwechslung von Kombination und Variation: Sobald Reihenfolge eine Rolle spielt, muss man Variation oder Permutation verwenden.
• Vergessen der Wiederholungen: Sind Elemente identisch, muss man die entsprechenden Fakultäten im Nenner berücksichtigen.
• Zu schnelles Rechnen: Olympiadeaufgaben sind oft so konstruiert, dass eine naive Formelanwendung nicht ausreicht. Fallunterscheidungen oder das Komplementprinzip (Gesamtanzahl minus unerwünschte Fälle) führen häufig schneller ans Ziel.

Das Komplementprinzip ist besonders nützlich: Wenn es einfacher ist, die "schlechten" Fälle zu zählen, zieht man sie von der Gesamtanzahl ab. Klassische Formulierung: "Wie viele Anordnungen von 5 Personen gibt es, bei denen zwei bestimmte Personen nicht nebeneinander stehen?" Statt direkt zu zählen, bestimmt man alle Anordnungen (5! = 120) und subtrahiert jene, bei denen die zwei zusammen stehen (2 · 4! = 48), was 72 ergibt.

Empfehlenswerte Vorbereitung

Wer sich systematisch vorbereiten möchte, findet beim Skript der Schweizer Mathematik-Olympiade zur Kombinatorik ausgezeichnetes Material auf Deutsch – inklusive Beweise, Aufgaben und Lösungshinweisen auf olympiadegerechtem Niveau.

Entscheidend ist nicht das bloße Auswendiglernen von Formeln, sondern das Erkennen, welche Struktur eine Aufgabe hat. Ist die Reihenfolge relevant? Gibt es Wiederholungen? Können Elemente mehrfach verwendet werden? Wer sich diese drei Fragen zur Gewohnheit macht, hat den schwierigsten Teil der kombinatorischen Olympiadeaufgaben schon gelöst.