Zählen ohne Aufzählung
Die Kombinatorik beantwortet „wie viele?“, wenn eine vollständige Auflistung aller Anordnungen unmöglich wäre. Drei klassische Fragen dominieren die einführende Zähltheorie: Permutationen (Reihenfolge zählt), Kombinationen (Reihenfolge zählt nicht) und Anordnungen / partielle Permutationen (Reihenfolge zählt, aber Sie füllen nur k von n Plätzen). Zu jeder Frage gibt es eine Variante mit und ohne Wiederholung.
Ein konkreter Einstieg ist Kombinationen ohne Wiederholung—der Binomialkoeffizient „n über k“—, von dem aus Sie je nach Problem zu geordneten und wiederholungszugelassenen Verwandten abzweigen.
Entscheidungshilfe
Fragen Sie der Reihe nach:
- Zählt die Reihenfolge? Wenn ja → Permutationen / Anordnungen. Wenn nein → Kombinationen.
- Darf dasselbe Element mehrfach vorkommen? Wenn ja → Formeln „mit Wiederholung“. Wenn nein → „ohne Wiederholung“.
- Ordnen Sie alle n Elemente an oder nur k davon? Volle Permutationen nutzen n!; partielle Auswahlen nutzen fallende Fakultäten oder n^k.
Jede dieser drei Achsen falsch zu lesen ist die übliche Quelle für Faktorfehler in Hausaufgaben und Interviewaufgaben.
Rechnerfamilie
- Permutationen ohne Wiederholung — n! geordnete Anordnungen von n verschiedenen Elementen.
- Permutationen mit Wiederholung — Multimengen-Permutationen n! / (r₁! r₂! …), wenn identische Kopien existieren.
- Kombinationen ohne Wiederholung — C(n, k) = n! / (k! (n − k)!) ungeordnete k-Teilmengen.
- Kombinationen mit Wiederholung — C(n + k − 1, k) Multimengen der Größe k aus n Typen.
- Anordnungen ohne Wiederholung — P(n, k) = n! / (n − k)! geordnete k-Tupel ohne Wiederverwendung.
- Anordnungen mit Wiederholung — n^k geordnete k-Tupel mit erlaubter Wiederverwendung.
Eingaben sind nichtnegative Ganzzahlen mit den üblichen Definitionsbereichsprüfungen (k ≤ n, wenn Wiederholung verboten ist, usw.). Überlaufende Fakultäten erscheinen als Rechenfehler statt als stilles Unendlich.
Fakultäten als gemeinsame Grundlage
Formeln ohne Wiederholung stützen sich auf n!—das Produkt 1 × 2 × … × n, mit 0! = 1 per Konvention. Kombinationen kürzen die interne Ordnung jeder Teilmenge (k!) und manchmal den ungenutzten Rest ((n − k)!) heraus. Partielle Permutationen behalten die Ordnung, teilen also nur durch (n − k)!.
Kombinationen mit Wiederholung nutzen die „stars and bars“-Identität C(n + k − 1, k). Anordnungen mit Wiederholung sind noch einfacher: jede der k Positionen wählt unabhängig eines von n Symbolen → n^k.
Kurzbeispiele
Spiel mit 52 Karten, Hand aus 5 (Reihenfolge egal, ohne Zurücklegen): C(52, 5).
Rennen mit 8 Läufern, Gold/Silber/Bronze: P(8, 3) = 8 × 7 × 6.
PIN mit 4 Ziffern, Ziffern dürfen wiederholt werden: 10^4 = 10000.
Buchstabanordnungen von „BOOK“: 4! / 2! wegen der beiden O—Multimengen-Permutation.
3 Kugeln aus 5 Sorten, Wiederholung erlaubt, Reihenfolge egal: C(5 + 3 − 1, 3).
Ein Wortproblem dem richtigen Rechner zuzuordnen ist die Fähigkeit; die Arithmetik ist sekundär.
Beziehungen, die Fehler vermeiden
- P(n, k) = C(n, k) × k! — erst die Menge wählen, dann ordnen.
- n! = P(n, n) — volle Permutationen sind partielle Permutationen mit k = n.
- C(n, k) = C(n, n − k) — Symmetrie der Binomialkoeffizienten.
- Wiederholung verbieten, wenn die Aufgabe sie erlaubt, führt zu Unterzählung; erlauben, wenn sie verboten ist, zu Überzählung.
Wo diese Zählungen vorkommen
- Wahrscheinlichkeitsnenner (faire Spiele, Stichproben)
- Skizzen zur Passwort- und Kennungsstärke (mit klaren Bedrohungsmodell-Hinweisen)
- Algorithmenanalyse (Suchräume, Zustandszählung)
- Versuchsplanung (Behandlungskombinationen)
- Sportliche „Möglichkeiten zum Ziel“ und ähnliche Rangfolgerätsel—als Mathematik, nicht als Wettberatung
Großes n wächst schneller als die Intuition. C(60, 6) sind bereits Millionen; Fakultäten über bescheidenes n hinaus überlaufen Gleitkommazahlen—daher dedizierte Helfer und Big-Integer-Bibliotheken in produktiven Systemen.
Lehrreihenfolge
- Permutationen kleiner n durch Aufzählen zählen, dann n! einführen.
- P(n, k) mit Podiumsbeispielen einführen.
- C(n, k) zeigen, indem man die Ordnung herausdividiert.
- Wiederholung ergänzen: zuerst n^k (unabhängige Positionen), dann stars and bars.
- Erst danach Multimengen-Permutationen mit wiederholten Buchstaben.
Direkt zu sechs ähnlich aussehenden Formeln ohne Entscheidungshilfe zu springen erzeugt mechanisches Einsetzen ohne Verständnis.
Implementierungshinweise
C(n, k) über drei volle Fakultäten zu berechnen ist einfach, überläuft aber früh. Multiplikative Algorithmen verkleinern Zwischenwerte. Die Helfer dieses Hubs nutzen Fakultätsdivision mit Endlichkeitsprüfungen für interaktives Lernen—nicht für kryptografische Größenordnungen von n. Nicht-Ganzzahlen und unmögliche (n, k)-Paare mit stabilen Fehlergründen ablehnen.
Häufige Fallstricke
- „Ausschuss aus 5“ als Permutation behandeln
- n^k für Ziehungen ohne Zurücklegen verwenden, wenn die Reihenfolge egal ist
- Fakultäten identischer Buchstaben in Wortproblemen vergessen
- Kombinationen mit Wiederholung mit Kombinationen ohne Wiederholung verwechseln beim Einkauf „bis zu k Artikel“
Zusammenfassung
Dieser Hub bündelt sechs elementare Zählwerkzeuge: volle und Multimengen-Permutationen, Kombinationen mit und ohne Wiederholung sowie partielle Anordnungen mit und ohne Wiederholung. Entscheiden Sie, ob Reihenfolge und Wiederverwendung gelten, wählen Sie die passende Formel und prüfen Sie mit einer kleinen Aufzählung. Die Rechner übernehmen die Arithmetik, damit Sie sich auf die korrekte Modellierung der Aufgabe konzentrieren können.