Kombinatorik.

Kombinatorik zählt, wie viele Möglichkeiten es gibt, Objekte anzuordnen oder auszuwählen. Die Antwort hängt von zwei Fragen ab: wird die Reihenfolge berücksichtigt, und sind Wiederholungen erlaubt? Aus den 2 × 2 Antworten ergeben sich vier Standardformeln für die typischen Klausuraufgaben.

Die vier Fälle die du in der Klausur kennen musst, sortiert nach den zwei Schlüsselfragen:

• Variation ohne Wiederholung (mit Reihenfolge, ohne Wdh): n!/((n-k)!), k aus n geordnet ziehen, z.B. 3 Bücher aus 10 anordnen
• Variation mit Wiederholung (mit Reihenfolge, mit Wdh): n^k, z.B. 4-stellige PIN aus 10 Ziffern: 10⁴ = 10 000
• Kombination ohne Wiederholung (ohne Reihenfolge, ohne Wdh): C(n,k) = n!/(k!(n-k)!), z.B. Lotto 6 aus 49
• Kombination mit Wiederholung (ohne Reihenfolge, mit Wdh): C(n+k-1,k), z.B. 3 Eiskugeln aus 4 Sorten

Spezialfall: bei Variation ohne Wdh mit k = n entsteht n!, die klassische Permutation aller Elemente (z.B. alle 5 Bücher anordnen: 5! = 120).

In Klausuren wirst du oft gefragt: wie viele Möglichkeiten gibt es?. Frage dich immer: spielt die Reihenfolge eine Rolle (z.B. Türschloss-Code: ja, Lotto-Zahlen: nein)? Sind Wiederholungen erlaubt (z.B. PIN: ja, Lotto: nein)? Daraus ergibt sich die richtige Formel.

Das Problem

Du sollst zählen, wieviele Möglichkeiten es gibt:

• Lotto 6 aus 49, wieviele Tipps?
• 4-stellige PIN, wieviele PINs?
• 3 Bücher aus 10 anordnen, wieviele Anordnungen?
• 3 Eiskugeln aus 4 Sorten (Sorten dürfen mehrfach), wieviele Becher?

Auf den ersten Blick völlig unterschiedlich. Aber alle vier sind dieselbe Frage in verschiedenen Verkleidungen, und alle haben eine kompakte Formel.

Kombinatorik ist die Mathematik des Zählens. Statt alle Möglichkeiten aufzuschreiben (was ab 100 unmöglich wird), nutzt man Formeln.

Die zwei Schlüsselfragen

Bei jeder Kombinatorik-Aufgabe musst du dir zwei Fragen stellen:

Zwei Fragen mit je 2 Antworten = 4 Fälle = 4 Formeln. Die musst du für die Klausur kennen.

Die vier Formeln

Sei n die Anzahl der verfügbaren Items (z.B. 49 Lottozahlen) und k die Anzahl der gezogenen (z.B. 6 Lottozahlen).

Variation ohne Wiederholung

Reihenfolge wichtig, jedes Item höchstens einmal.

V_(ohne)(n, k) = n!/((n-k)!) = n · (n-1) ··· (n-k+1)

Beispiel: 3 Bücher aus 10 ins Regal stellen, in einer Reihe. 10!/7! = 10 · 9 · 8 = 720 Anordnungen.

Spezialfall: k = n (du verwendest alle Items). Dann ist es einfach n!, das ist die klassische Permutation. Beispiel: alle 5 Bücher anordnen → 5! = 120.

Variation mit Wiederholung

Reihenfolge wichtig, Items dürfen wiederholt werden.

V_(mit)(n, k) = n^k

Beispiel: 4-stellige PIN mit 10 Ziffern. 10⁴ = 10 000 PINs.

Wachstum ist exponentiell. PIN mit 6 Stellen: 10⁶ = 1 000 000, 100× mehr als 4 Stellen.

Kombination ohne Wiederholung

Reihenfolge egal, jedes Item höchstens einmal.

C(n, k) = C(n,k) = n!/(k!(n-k)!)

Sprich: "n über k" oder "Binomialkoeffizient".

Beispiel: Lotto 6 aus 49. C(49,6) = 49!/(6! · 43!) = 13 983 816 ≈ 14 Mio Tipps.

Daher Wahrscheinlichkeit für 6 Richtige = 1/(13 983 816) ≈ 7 · 10^(-8).

Kombination mit Wiederholung

Reihenfolge egal, Items dürfen wiederholt werden.

C^*(n, k) = C(n+k-1,k)

Beispiel: 3 Eiskugeln aus 4 Sorten (gleiche Sorten erlaubt). C(4+3-1,3) = C(6,3) = 20 Becher.

Klausur-Falle: gleiche Sorten erlaubt heißt Multimenge, nicht Tupel, Reihenfolge egal!

Wie unterscheide ich die 4 Fälle in der Klausur?

Schritt 1: Lies die Aufgabe und frag dich:

Wenn ich (A, B, C) auswähle,
ist (B, A, C) das Gleiche oder etwas anderes?

→ "das Gleiche"           → Reihenfolge egal → KOMBINATION
→ "etwas anderes"         → Reihenfolge wichtig → VARIATION

Schritt 2: Frag dich:

Darf ich z.B. (A, A, A) wählen, also dasselbe Item mehrmals?

→ "ja"                    → mit Wiederholung
→ "nein"                  → ohne Wiederholung

Das gibt dir das Feld in der Entscheidungstabelle:

Spezialfall: bei k = n in Variation ohne Wdh wird daraus n!, die klassische Permutation aller Elemente.

Standardfälle aus der Klausur

1. Lotto 6 aus 49, Kombination ohne Wdh

• Reihenfolge egal (4-7-12 = 12-7-4)
• Ohne Wiederholung (Kugeln werden nicht zurückgelegt)
• → C(49,6) = 13 983 816

2. 4-stellige PIN aus 10 Ziffern, Variation mit Wdh

• Reihenfolge wichtig (1234 ≠ 4321)
• Mit Wiederholung (1111 erlaubt)
• → 10⁴ = 10 000

3. 5 Bücher anordnen, Permutation (Spezialfall Variation ohne Wdh, k = n)

• Reihenfolge wichtig
• Ohne Wiederholung (jedes Buch genau einmal)
• → 5! = 120

4. 3 Eiskugeln aus 4 Sorten (Sorten mehrfach), Kombination mit Wdh

• Reihenfolge egal (Schoko-Vanille = Vanille-Schoko)
• Mit Wiederholung (3× Schoko OK)
• → C(4+3-1,3) = C(6,3) = 20

5. Bonus: 3 Bücher aus 10 in einer Reihe ins Regal, Variation ohne Wdh

• Reihenfolge wichtig (welches Buch links, welches rechts)
• Ohne Wiederholung (jedes Buch nur einmal)
• → 10!/7! = 10 · 9 · 8 = 720

Die Fakultät n!

n! heißt n-Fakultät und ist das Produkt aller natürlichen Zahlen bis n:

n! = n · (n-1) · (n-2) ··· 2 · 1

Wichtig: 0! = 1 per Definition (kein Tippfehler). Sonst würden viele Formeln nicht klappen.

0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5\,040
8! = 40\,320
9! = 362\,880
10! = 3\,628\,800

Fakultäten wachsen schnell. 20! > 10^(18). Bei großen Zahlen: vereinfachen, kürzen, nicht ausrechnen.

Faktor-Vereinfachung (häufig in Klausuren): 10!/8! = (10 · 9 · cancel8!)/(cancel8!) = 10 · 9 = 90

Nie 10! vollständig ausschreiben, kürzen!

Der Binomialkoeffizient näher

C(n,k) wird in der Schule oft auch "Pascal-Dreieck-Zahl" genannt. Eigenschaften:

binom(n, 0)   = 1                 (eine leere Auswahl)
binom(n, n)   = 1                 (alles auswählen)
binom(n, 1)   = n                 (eine aus n)
binom(n, k)   = binom(n, n-k)     (Symmetrie!)

Die Symmetrie ist Klausur-Trick: C(49,43) = C(49,6), viel leichter!

Pascal-Dreieck:

              1
            1   1
          1   2   1
        1   3   3   1
      1   4   6   4   1
    1   5  10  10   5   1
  1   6  15  20  15   6   1

Jede Zahl ist Summe der zwei darüber. Zeile n enthält C(n,0), C(n,1), ..., C(n,n).

Klausur-Tricks

Trick 1, Frage-Pipeline: Bei jeder Aufgabe genau zwei Fragen stellen:

1. Reihenfolge wichtig? (Variation/Permutation vs. Kombination)
2. Wiederholung erlaubt? (mit vs. ohne)

Beide Antworten geben dir die Formel. Nie raten.

Trick 2, "alle anordnen" = Variation ohne Wdh mit k=n = n! (klassische Permutation).

Trick 3, "k aus n ziehen, ohne Reihenfolge" = Lotto-Formel = C(n,k).

Trick 4, Symmetrie ausnutzen: C(49,43) ist gleich C(49,6), viel kleinere Rechnung.

Trick 5, Faktoren kürzen, NIE Fakultäten vollständig ausrechnen:

10! / 7!   →   10 · 9 · 8     (nicht 3.628.800 / 5.040)

Trick 6, Verbundene Aufgaben: "Wie viele 4-stellige PINs ohne 0?" → 9⁴ = 6 561 (statt 10 Ziffern jetzt 9). Anpassung von n, der Rest bleibt.

Trick 7, Ergänzungs-Trick: "Wie viele Lotto-Tipps mit mindestens einer Zahl unter 10?" → über Gegenereignis: alle Tipps − Tipps ohne Zahl unter 10 = C(49,6) - C(40,6).

Trick 8, Bei Code/Passwörtern: Anzahl Stellen = k, verschiedene Zeichen = n, Wiederholung meist erlaubt → n^k.

Wo brauchst du Kombinatorik?

• Wahrscheinlichkeit: Laplace-Formel braucht Kombinatorik im Zähler und Nenner. "P(2 Asse aus 4 Karten gezogen)" = C(?,?) / C(?,?).
• Kryptographie: wieviele Schlüssel hat ein 256-Bit-Schlüssel? 2^(256).
• Datenbanken / Anfrageoptimierung: wieviele Joins-Reihenfolgen bei 10 Tabellen? 10!.
• Genetik: Anzahl möglicher Kombinationen bei Erbgang.
• Game-Design: wieviele unterschiedliche Decks aus 60 Karten lassen sich aus 200 wählen? C(200,60).
• Logistik: Reihenfolge-Probleme (Travelling Salesman) sind Permutations-Probleme, alle n Städte werden besucht, gesucht ist die Anzahl Reihenfolgen n!.

Faustregel: Wenn du in der Klausur eine "Wieviele Möglichkeiten?"-Frage liest, ist es zu 95 % einer der vier Fälle. Entscheidungstabelle im Kopf, dann Formel anwenden.

Kombinatorik-Explorer

Klick einen der vier Fälle, stell n und k ein, sieh:

• Die Formel mit eingesetzten Werten
• Die Anzahl der Möglichkeiten
• Eine Aufzählung der ersten 60 (nützlich um zu sehen warum es so viele/wenige sind)

Probier folgendes:

• Variation ohne Wdh, n=3, k=3 → 6 Möglichkeiten: alle Anordnungen von ABC (das ist die klassische Permutation 3!)
• Variation mit Wdh, n=2, k=4 → 2⁴ = 16: alle 4-stelligen Wörter aus A/B
• Kombination ohne Wdh, n=5, k=2 → 10: Paare ohne Reihenfolge
• Kombination mit Wdh, n=3, k=4 → 15: Multimengen mit Wiederholung

Beobachte den Unterschied zwischen (A,B) und {A,B}, Tupel mit Reihenfolge vs. Mengen ohne.

Faustregel zum Mitnehmen: Zwei Fragen: Reihenfolge wichtig? Wiederholung erlaubt? Daraus folgt die Formel. Die Entscheidungstabelle ist das wichtigste Werkzeug der Stochastik-Klausur.