Lektion 36 — Fundamentales Zählprinzip

FZP und Bäume

Aussage

Besteht ein Experiment aus $k$ aufeinanderfolgenden, unabhängigen Schritten mit $n_1$ Ergebnissen im ersten, $n_2$ im zweiten, …, $n_k$ im $k$-ten Schritt, dann ist die Gesamtzahl der möglichen Ergebnisse: $N = n_1 \cdot n_2 \cdots n_k$

Additionsprinzip (Alternative)

Wenn eine Aufgabe durch Methode A in $m$ Wegen ODER durch Methode B in $n$ Wegen (sich gegenseitig ausschließend) erledigt werden kann, ist die Gesamtzahl $m + n$.

Archetypisches Beispiel

Passwort mit 4 Zeichen: jedes A-Z (26 Optionen). Gesamt: $26^4 = 456\,976$.

Möglichkeitsbaum

Jeder Schritt „verzweigt" — der Baum hat $n_1$ Wurzeln, jede mit $n_2$ Kindern usw. Blätter = Gesamtanzahl der Ergebnisse.

Restriktionen — „ohne Wiederholung"

Wenn Schuhe nicht wiederholbar sind, hat der erste 5 Optionen, der zweite 4, der dritte 3 — Kombinationen ohne Wiederholung. Verallgemeinerung zur Variation (Lektion 37).

Funktionen zwischen Mengen

• Gesamtzahl der Funktionen $f: A \to B$ mit $|A| = m, |B| = n$: $n^m$.
• Injektive Funktionen ($f: A \to B$ mit $m \leq n$): $n!/(n-m)!$ (Variation).
• Bijektive Funktionen ($m = n$): $n!$ (Permutation).