Das Zählprinzip
Multiplikationsprinzip: Kann ein Ereignis auf m Arten eintreten und danach ein zweites auf n Arten, dann können beide nacheinander auf m × n Arten eintreten. Das gilt auch für drei oder mehr Ereignisse.
Beispiel: Ein Schloss hat 3 Ringe mit den Ziffern 0–9. Codes = 10 × 10 × 10 = 1000.
Additionsprinzip: Kann man eine Aufgabe auf m Arten oder auf n anderen Arten erledigen (nicht beides), dann gibt es m + n Möglichkeiten. „Und“ heißt multiplizieren, „oder“ heißt addieren.
Fakultät
n! (gesprochen „n Fakultät“) = 1 × 2 × 3 × … × n für eine natürliche Zahl n. Also 3! = 6, 4! = 24, 5! = 120, 6! = 720.
- Wir legen 0! = 1 fest. So stimmen Formeln wie ⁿPₙ = n!/0! weiterhin.
- n! = n × (n − 1)!, also 7!/5! = 7 × 6 = 42. Kürze lieber, statt alles auszumultiplizieren.
Permutationen: die Formel für nPr
Eine Permutation ist eine Anordnung in fester Reihenfolge. Wir ordnen r Objekte aus n verschiedenen Objekten an (ohne Wiederholung): Der erste Platz hat n Möglichkeiten, der zweite n − 1, …, der r-te hat n − r + 1. Also
ⁿPᵣ = n(n − 1)(n − 2)…(n − r + 1) = n!/(n − r)!, 0 ≤ r ≤ n.
- ⁿPₙ = n! (alle anordnen). ⁿP₀ = 1.
- Sind Wiederholungen erlaubt, gibt es nʳ Anordnungen.
- Sind unter n Objekten p gleiche der einen Art, q gleiche einer anderen Art und so weiter, dann gibt es für alle n genau n!/(p! q! …) Anordnungen. Beispiel: MISSISSIPPI hat 11 Buchstaben mit I×4, S×4, P×2, also 11!/(4!·4!·2!) = 34650.
Kombinationen: die Formel für nCr und der Zusammenhang mit nPr
Eine Kombination ist eine Auswahl, bei der die Reihenfolge egal ist. Jede Auswahl von r Objekten lässt sich auf r! Arten ordnen, und alle Auswahlen zusammen ergeben alle ⁿPᵣ Anordnungen. Also
ⁿPᵣ = ⁿCᵣ × r!, und daraus folgt ⁿCᵣ = n!/(r!(n − r)!).
- ⁿC₀ = ⁿCₙ = 1.
- ⁿCᵣ = ⁿCₙ₋ᵣ: r zum Mitnehmen wählen = n − r zum Dortlassen wählen (Schritt 5 im 3D). Wenn also ⁿCₐ = ⁿC_b, dann ist a = b oder a + b = n.
- ⁿCᵣ + ⁿCᵣ₋₁ = ⁿ⁺¹Cᵣ (Pascal-Regel, die beim Binomischen Lehrsatz wiederkommt).
Einfache Anwendungen: was nehme ich wann?
Frage dich: Ändert die Reihenfolge das Ergebnis? Sitzordnung, Rangliste, Zahlen oder Wörter bilden, Passwörter → Permutation. Teams, Ausschüsse, Händeschütteln, Aufgaben auswählen, Obstgruppen → Kombination.
- Händeschütteln bei 10 Personen: ¹⁰C₂ = 45.
- Diagonalen eines n-Ecks: ⁿC₂ − n.
- Wörter aus den Buchstaben eines Wortes mit Bedingungen (Vokale zusammen: als einen Block behandeln, dann mit den Anordnungen innerhalb des Blocks multiplizieren).
- Fragen mit „mindestens“ oder „höchstens“: die einzelnen Fälle addieren.
Worauf es in der Prüfung ankommt
Das kommt typischerweise dran: n aus einer Gleichung wie ⁿP₄ = 12 · ⁿP₂ bestimmen (2–3 Punkte), Buchstaben mit Wiederholungen oder Bedingungen anordnen (3–4 Punkte), Ausschüsse mit „mindestens“ (3–4 Punkte) und Aufgaben im Stil von ⁿCᵣ = ⁿCₙ₋ᵣ (1–2 Punkte). Schreibe die Zählidee in Worten hin, bevor du die Zahlen einsetzt.
Wichtige Formeln und Definitionen
- Zählprinzip: m Arten, dann n Arten → m × n Arten
- n! = 1 × 2 × … × n, 0! = 1, n! = n(n − 1)!
- ⁿPᵣ = n!/(n − r)!; mit Wiederholung nʳ
- Gleiche Objekte: n!/(p! q! r! …)
- ⁿCᵣ = n!/(r!(n − r)!), ⁿPᵣ = ⁿCᵣ · r!
- ⁿCᵣ = ⁿCₙ₋ᵣ; ⁿCᵣ + ⁿCᵣ₋₁ = ⁿ⁺¹Cᵣ
Gelöste Beispiele
1. Wie viele 3-stellige Zahlen lassen sich aus den Ziffern 1, 2, 3, 4, 5 bilden, wenn (i) Ziffern sich wiederholen dürfen (ii) Ziffern sich nicht wiederholen dürfen?
(i) Jede Stelle hat 5 Möglichkeiten: 5 × 5 × 5 = 125. (ii) 5 Möglichkeiten, dann 4, dann 3: 5 × 4 × 3 = 60 = ⁵P₃.
2. Berechne 8!/(6! × 2!).
8! = 8 × 7 × 6!, also 8!/6! = 56. Durch 2! = 2 teilen: 56/2 = 28 (das ist ⁸C₂).
3. Auf wie viele Arten können 6 Personen in einer Reihe mit 6 Stühlen sitzen? Bei wie vielen davon sitzen die zwei Freunde A und B nebeneinander?
Alle: 6! = 720. Nebeneinander: Klebe A und B zu einem Block zusammen, das ergibt 5 Einheiten, die auf 5! = 120 Arten angeordnet werden. Im Block können A und B tauschen: 2! = 2. Insgesamt 120 × 2 = 240.
4. Wie viele verschiedene Wörter (mit oder ohne Sinn) lassen sich aus allen Buchstaben von BANANA bilden?
6 Buchstaben: B×1, A×3, N×2. Wörter = 6!/(3! · 2!) = 720/12 = 60.
5. Bestimme n, wenn ⁿP₅ = 42 · ⁿP₃ (n > 4).
n(n−1)(n−2)(n−3)(n−4) = 42 · n(n−1)(n−2). Kürzen: (n − 3)(n − 4) = 42 = 7 × 6. Also n − 3 = 7, n = 10.
6. Aus 6 Männern und 5 Frauen soll ein Ausschuss aus 3 Männern und 2 Frauen gewählt werden. Auf wie viele Arten geht das?
Männer: ⁶C₃ = 20. Frauen: ⁵C₂ = 10. Beides wird gebraucht („und“), also multiplizieren: 20 × 10 = 200.
7. Wenn ⁿC₉ = ⁿC₈, bestimme ⁿC₁₇.
ⁿCₐ = ⁿC_b mit a ≠ b bedeutet a + b = n, also n = 17. Dann ist ¹⁷C₁₇ = 1.
8. Aus 4 roten und 5 blauen Kugeln sollen 3 Kugeln gewählt werden, darunter mindestens 2 rote. Auf wie viele Arten geht das?
Fall 2 rote + 1 blaue: ⁴C₂ × ⁵C₁ = 6 × 5 = 30. Fall 3 rote: ⁴C₃ = 4. Die Fälle sind getrennt („oder“), also addieren: 30 + 4 = 34.
Häufige Fehler
- nPr für Teams oder Ausschüsse benutzen. Wenn das Vertauschen zweier gewählter Personen dieselbe Gruppe ergibt, nimm nCr.
- Addieren, wo man multiplizieren muss. „Dies und dann das“ wird multipliziert, „dies oder das“ wird addiert.
- Vergessen, durch die Fakultäten der wiederholten Buchstaben zu teilen, etwa bei APPLE oder BANANA.
- Glauben, dass 0! = 0 ist. Per Definition gilt 0! = 1.