Kombinatorik

Darum geht's

Wie viele Möglichkeiten gibt es, $13$ Schüler in einer Reihe aufzustellen? Wie viele vierstellige PINs gibt es? Wie viele verschiedene Tipps beim Lotto ”$6$ aus $45$”? Die Antworten finden sich in der Kombinatorik — der Kunst, Anzahlen systematisch zu zählen, ohne sie alle aufzuschreiben.

Dieses Kapitel ist die Grundlage für die Wahrscheinlichkeitsrechnung und die Binomialverteilung — wer die Anzahl der möglichen Fälle nicht zählen kann, kann auch keine Laplace-Wahrscheinlichkeit berechnen.

Worum geht es?

Die zentrale Idee der Kombinatorik ist das Zählprinzip: Wenn ein Vorgang aus mehreren unabhängigen Schritten besteht, multiplizieren sich die Möglichkeiten. Bei einer PIN aus $4$ Ziffern ($0$ bis $9$) hast du $10 \cdot 10 \cdot 10 \cdot 10 = 10^4 = 10\,000$ Möglichkeiten.

Daraus ergeben sich die vier wichtigen Grundsituationen — unterschieden danach, ob (a) die Reihenfolge zählt und ob (b) Zurücklegen erlaubt ist:

• Mit Reihenfolge, mit Zurücklegen — PINs, Kennzeichen: $n^k$ Möglichkeiten.
• Mit Reihenfolge, ohne Zurücklegen — Anordnung von Personen, Medaillenränge: $n \cdot (n-1) \cdots (n-k+1) = \tfrac{n!}{(n-k)!}$.
• Ohne Reihenfolge, ohne Zurücklegen (“mit einem Griff” / Lotto): $\binom{n}{k} = \tfrac{n!}{k!(n-k)!}$.
• Ohne Reihenfolge, mit Zurücklegen — seltener Fall, in der Schule meist nur erwähnt.

Der Binomialkoeffizient $\binom{n}{k}$ — gelesen ”$n$ über $k$” — ist das Herzstück des Kapitels und erscheint später auch bei der Binomialverteilung. Er zählt, auf wie viele Arten du $k$ Objekte aus $n$ Objekten auswählen kannst, ohne auf die Reihenfolge zu achten.

Der Fakultätsbegriff $n! = 1 \cdot 2 \cdot 3 \cdots n$ liefert die Anzahl aller Permutationen von $n$ verschiedenen Objekten. $0!$ ist per Definition $1$ — eine Konvention, die viele Formeln sauber macht.

Was du schon können solltest

Für dieses Kapitel brauchst du:

• erste Erfahrung mit dem Zählen von Ergebnissen aus der Wahrscheinlichkeitsrechnung der 7./8. Klasse,
• sicheres Rechnen mit Brüchen (Binomialkoeffizienten werden über Bruch- und Fakultätsausdrücke berechnet),
• Grundkenntnisse zu Baumdiagrammen,
• Routine im Umgang mit dem Taschenrechner (Taste $n!$ und $\binom{n}{k}$).

Was du in diesem Kapitel lernst

Drei Lektionen, die die vier Standardfälle sauber voneinander trennen:

1. Anzahlen bestimmen — das Multiplikationsprinzip, Permutationen ohne Wiederholung, Fakultät.
2. Ziehen mit und ohne Zurücklegen — die beiden klassischen Urnenmodelle: $n^k$ bei “mit”, $n \cdot (n-1) \cdots$ bei “ohne”.
3. Ziehen mit einem Griff — der Binomialkoeffizient $\binom{n}{k}$. Standard für Lotto, Kartenhände, Auswahlkombinationen.

Eine wichtige Technik in allen Lektionen: Bevor du rechnest, identifiziere den Fall: “Zählt die Reihenfolge? Wird zurückgelegt?” Diese zwei Fragen bestimmen die Formel.

Wichtige Begriffe im Überblick

• Permutation — Anordnung von $n$ verschiedenen Objekten: $n!$ Möglichkeiten.
• Fakultät — $n! = 1 \cdot 2 \cdots n$; $0! = 1$.
• Variation — Anordnung von $k$ aus $n$: $\tfrac{n!}{(n-k)!}$.
• Kombination — Auswahl von $k$ aus $n$ ohne Reihenfolge: $\binom{n}{k}$.
• Binomialkoeffizient ($\binom{n}{k}$) — ”$n$ über $k$”. $\binom{n}{k} = \tfrac{n!}{k!(n-k)!}$.
• Zählprinzip — bei unabhängigen Schritten multiplizieren sich die Möglichkeiten.

Häufige Denkfehler

Achtung

Der Unterschied zwischen “Reihenfolge zählt” und “Reihenfolge zählt nicht” ist der Angelpunkt der Kombinatorik. Die typische Frage zur Diagnose: Ist "$\text{ABC}$" dieselbe Auswahl wie "$\text{CBA}$"? Bei Ranglisten nein, bei Komitees ja.

1. ”$\binom{n}{k} = \binom{k}{n}$.” Nur in Sonderfällen. Richtig ist die Symmetrie $\binom{n}{k} = \binom{n}{n-k}$. Aus $8$ Personen $3$ auswählen ist dasselbe wie $5$ “übrig lassen”: $\binom{8}{3} = \binom{8}{5} = 56$.
2. “Lotto ’$6$ aus $45$’ hat $45^6$ Möglichkeiten.” Nein — das wäre “mit Reihenfolge, mit Zurücklegen”. Beim Lotto werden ohne Zurücklegen gezogen und die Reihenfolge spielt keine Rolle. Also $\binom{45}{6} \approx 8{,}1$ Millionen.
3. “Zwei Einsen unterscheiden sich in einer Ziffernfolge nicht.” Bei Buchstaben mit Wiederholung (etwa im Wort $\text{MATHEMATIK}$) musst du durch die Fakultät der identischen Buchstaben teilen. Ohne diese Korrektur zählst du zu viel.

Wo es im Lehrplan 21 steht

Kombinatorik gehört zu MA.3 – Grössen, Funktionen, Daten, 3. Zyklus:

• MA.3.D.3 – Anzahlen kombinatorisch bestimmen (Produktregel, Permutation, Kombination).
• MA.3.B.4 – Kombinatorische Argumente zur Begründung von Wahrscheinlichkeiten einsetzen.

Das Zählprinzip und einfache Permutationen gelten als Grundanspruch im 3. Zyklus. Binomialkoeffizient und anspruchsvollere Urnenmodelle gehören zur Erweiterung und werden im Gymnasium mit der Binomialverteilung verbunden.

Die Themen im Überblick

• Anzahlen bestimmen: Systematisch zählen
• Ziehen mit und ohne Zurücklegen
• Ziehen mit einem Griff

Quellen

• Lehrplan 21 — Mathematik — Deutschschweizer Erziehungsdirektoren-Konferenz (D-EDK)
• Lehrplan Volksschule Aargau — Mathematik — Kanton Aargau, Departement Bildung, Kultur und Sport