Kombinatorik und Wahrscheinlichkeit · Ratgeber von Eqora
Kombinationen berechnen: Wann zählt die Reihenfolge?
Ein Team auswählen und Aufgaben darin verteilen sind verschiedene Ergebnisse. Leite die Formel her und prüfe Auswahlen mit Nebenbedingungen.
Aus acht Freiwilligen soll ein dreiköpfiges Team entstehen. Das Produkt 8 × 7 × 6 ergibt 336, tatsächlich gibt es aber nur 56 verschiedene Teams. Beide Zahlen haben eine Bedeutung: Das Produkt unterscheidet eine erste, zweite und dritte Person; beim Team zählt nur die Zusammensetzung. Wer Kombinationen berechnen möchte, muss solche mehrfach gezählten Anordnungen erkennen. Entscheidend ist deshalb zuerst die Frage, was genau als ein fertiges Ergebnis gelten soll.
Wir zählen zunächst geordnete Auswahlen und erklären, warum jedes Team dabei sechsmal vorkommt. Daraus entsteht die Formel für den Binomialkoeffizienten. Anschließend verändern wir die Regeln: feste Rollen, Qualifikationen, Wiederholungen und begrenzte Vorräte führen nicht automatisch zum gleichen Modell. Alle Beispiele lassen sich auf Papier ohne App bearbeiten. Du brauchst kein Signalwort zu erraten, sondern musst entscheiden können, ob zwei Beschreibungen dasselbe Ergebnis darstellen oder tatsächlich verschiedene Möglichkeiten sind.
Eqora veröffentlicht diesen Leitfaden als Lernhilfe, nicht als Ersatz für Prüfungsarbeit oder Garantie für richtige Ergebnisse und Noten. Prüfe Aufgabenstellung, Notation, Voraussetzungen und Ergebnis selbst. Die Wüstenfotos veranschaulichen Auswählen, Gruppieren und Anordnen. Sie sind keine numerischen Diagramme: Anzahl und Farbe der sichtbaren Clips legen keine Beispieldaten fest. Für die Rechnungen gelten ausschließlich die ausdrücklich genannten, erfundenen Personen und Gegenstände sowie die jeweils beschriebenen Auswahlregeln.
Kombinationen berechnen heißt Gruppen zählen
Die acht Freiwilligen sind unterscheidbare Personen, und niemand darf zweimal im selben Team vorkommen. Nennen wir drei ausgewählte Menschen A, B und C. Die Listen ABC und BAC beschreiben dasselbe Team, solange alle Mitglieder gleichberechtigt sind. Eine andere Schreibreihenfolge verändert die Zugehörigkeit nicht. Auch wenn die Personen nacheinander ausgewählt werden, kann das fertige Ergebnis also eine ungeordnete Menge sein. Der zeitliche Ablauf allein entscheidet nicht darüber, ob die Reihenfolge beim Zählen berücksichtigt werden muss.
Überlege, welche Information das Ergebnis behalten soll. Ein Team hält die Mitgliedschaft fest, ein Siegerpodest zusätzlich die Platzierung. Bei einem Ausschuss mit Vorsitz ist eine Rolle ausgezeichnet. In allen drei Aufgaben kann das Wort „auswählen“ stehen; als Entscheidungshilfe reicht es nicht. Unser Leitfaden zum Verstehen von Textaufgaben zeigt, wie du die gesuchte Größe von beiläufigen Angaben trennst. Beschreibe eine einzelne gültige Möglichkeit, bevor du ihre Gesamtzahl mit einer Formel bestimmst.
Bei festen Rollen bleibt jeder Platz erhalten
Nun sollen drei verschiedene Personen Navigation, Protokoll und Koordination übernehmen. Für die Navigation gibt es acht Möglichkeiten, für das Protokoll noch sieben und für die Koordination sechs. Das Produktprinzip liefert 8 × 7 × 6 = 336 Rollenverteilungen. Vertauschen zwei Personen ihre Aufgaben, entsteht ein anderes Ergebnis, obwohl das Team gleich bleibt. Im Deutschen heißt eine solche geordnete Auswahl ohne erneute Verwendung meist Variation ohne Wiederholung. Eine Permutation bezeichnet häufig die Anordnung aller vorhandenen Objekte.
Für k verschiedene Plätze aus n unterscheidbaren Objekten ohne Wiederholung lautet das Produkt n(n − 1)…(n − k + 1). Es enthält k Faktoren, nicht n Faktoren. Die Schreibweise n!/(n − k)! ist eine Abkürzung dafür. Werden alle n Objekte angeordnet, bleibt n!. Bei drei ausgewählten Personen aus acht wäre 8! dagegen zu viel: Damit würdest du zusätzlich die fünf Personen anordnen, die gar keine der drei Rollen erhalten haben.
Warum die Division durch k Fakultät gerechtfertigt ist
Ein festes Team aus A, B und C erscheint in sechs Listen: ABC, ACB, BAC, BCA, CAB und CBA. Es gibt 3 × 2 × 1 = 3! Anordnungen. Jedes Team aus drei verschiedenen Menschen erzeugt genau gleich viele solcher Listen. Daher lassen sich die 336 geordneten Auswahlen in Sechsergruppen zusammenfassen: C(8,3) = 336/6 = 56. Wir teilen nicht einfach, weil das Ergebnis groß aussieht, sondern weil die gleichmäßige Mehrfachzählung vollständig erklärt ist.
Allgemein gilt C(n,k) = n!/[k!(n − k)!] für ganze Zahlen mit 0 ≤ k ≤ n. Derselbe Ausdruck wird als Binomialkoeffizient geschrieben und „n über k“ gelesen. Der Kombinatorikkurs der Universität Stuttgart beschreibt ihn als Anzahl der k-elementigen Teilmengen einer n-elementigen Menge. Im Teambeispiel entfernt k! die Anordnung der ausgewählten Personen. Der Faktor (n − k)! kürzt die nicht benötigten Faktoren am Ende von n! weg. Keine Person wird dadurch aus der tatsächlich ausgewählten Gruppe gestrichen.
Kürze früh und prüfe die Randfälle
Für drei Objekte aus zehn musst du keine riesigen Fakultäten ausrechnen. Kürze den gemeinsamen Teil zuerst: C(10,3) = (10 × 9 × 8)/(3 × 2 × 1) = 120. Eine Anzahl von Kombinationen ist eine nichtnegative ganze Zahl. Ein Bruchergebnis weist auf einen Rechenfehler oder ein unpassendes Modell hin. Lass den Nenner zusammen: Nur den letzten Faktor durch drei zu teilen ist etwas anderes, als das gesamte Produkt durch sechs zu teilen.
Es gibt genau eine leere Auswahl und genau eine Auswahl aller vorhandenen Objekte: C(n,0) = C(n,n) = 1. Das sind nicht null Möglichkeiten. Die Festlegung 0! = 1 sorgt dafür, dass die Formel dazu passt. Sind mehr als n verschiedene Personen ohne Wiederholung verlangt, ist keine Auswahl möglich; die Anzahl ist null. Setze dafür keine negative Fakultät in die elementare Formel ein. Prüfe außerdem, dass n und k ganze Anzahlen sind und keine Längen, Anteile oder Prozentwerte.
Zähle zur Kontrolle die ausgeschlossenen Personen
Ein Dreierteam aus acht bestimmt eindeutig die fünf Personen, die nicht teilnehmen. Umgekehrt bestimmt diese ausgeschlossene Fünfergruppe das Team. Deshalb gilt C(8,3) = C(8,5) = 56. Hinter der Gleichheit steht eine eindeutige Zuordnung, nicht nur eine zufällige Übereinstimmung. Zum Rechnen darfst du häufig die kleinere Zahl von k und n − k verwenden. Ein Dreierteam und seine ausgeschlossene Fünfergruppe enthalten natürlich nicht dieselben Menschen; sie beschreiben nur dieselbe Entscheidung aus entgegengesetzten Blickrichtungen.
Eine zweite Gegenprobe betrachtet eine bestimmte Person A. Ist A dabei, wählst du zwei der übrigen sieben: C(7,2) = 21. Ist A nicht dabei, wählst du drei aus diesen sieben: C(7,3) = 35. Die Fälle überschneiden sich nicht und decken alle Teams ab, also ergibt ihre Summe 56. Unser Leitfaden zur Ergebniskontrolle ohne Lösungsheft empfiehlt solche unterschiedlichen Denkwege. Dieselbe Fakultätsfolge zweimal in einen Rechner einzugeben prüft vor allem die Eingabe, nicht die ursprüngliche Modellwahl.
Nebenbedingungen verändern die zulässigen Gruppen
Jetzt besitzen drei der acht Personen ein bestimmtes Zertifikat, die anderen fünf nicht. Ein Team mit genau zwei Zertifizierten entsteht durch zwei Auswahlen: zwei aus der Dreiergruppe und eine aus der Fünfergruppe. Das ergibt C(3,2) × C(5,1) = 3 × 5 = 15 Teams. Multipliziere, weil jedes zulässige Paar mit jeder zulässigen dritten Person verbunden werden kann. Multipliziere nicht nochmals mit drei für deren Position: Eine solche Position gehört nicht zur Teamdefinition.
Bei mindestens einer zertifizierten Person ist die Gegenmenge einfacher. Alle Teams minus Teams ohne Zertifikat ergeben C(8,3) − C(5,3) = 56 − 10 = 46. Prüfe durch getrennte Fälle: Genau eine zertifizierte Person liefert C(3,1)C(5,2) = 30, genau zwei liefern 15 und genau drei liefern eins. Zusammen sind es 46. „Mindestens eine“ ist also nicht dasselbe wie „genau eine“: Ein Team mit zwei Zertifizierten erfüllt nur die erste dieser beiden Bedingungen.
Wiederholungen verlangen ein anderes Modell
Die gewöhnliche Formel C(n,k) setzt voraus, dass jedes unterscheidbare Objekt höchstens einmal gewählt wird. Für drei geordnete Plätze mit vier wiederverwendbaren Symbolen gibt es dagegen 4³ = 64 Folgen. Interessieren nur die Häufigkeiten der vier Symbolarten, ergeben sich C(6,3) = 20 ungeordnete Auswahlen mit Wiederholung. Stelle dir drei gleiche Markierungen und drei Trennzeichen vor: Die vier Zwischenräume legen fest, wie oft jede Symbolart vorkommt. Leere Zwischenräume bedeuten dabei eine Häufigkeit von null.
Die 20 entstehen nicht durch 64/3!. Drei verschiedene Symbole haben sechs Anordnungen, zwei gleiche und ein anderes haben drei, drei gleiche haben nur eine. Es gibt keine einheitliche Mehrfachzählung, die du herausdividieren könntest. Unbegrenzt wiederverwendbare Arten sind außerdem etwas anderes als einzelne Gegenstände aus einem begrenzten Vorrat. Bei Höchstmengen oder nicht unterscheidbaren Objekten musst du diese Bedingungen ausdrücklich modellieren. Die vertraute Formel ohne Erklärung weiterzuverwenden ist keine sichere Abkürzung.
Aus einer Anzahl folgt noch keine Wahrscheinlichkeit
Wenn jedes der 56 Dreierteams gleich wahrscheinlich ist, beträgt die Wahrscheinlichkeit für genau zwei Zertifizierte 15/56. Zähler und Nenner zählen dieselbe Art von Ergebnis: ungeordnete Teams. Der Bruch 15/336 würde Teamzahlen mit geordneten Rollenverteilungen vermischen. Du darfst auch geordnete Dreierlisten verwenden, musst dann aber die günstigen Listen passend mitzählen: 15 × 6 = 90. So entsteht 90/336 = 15/56 und damit dasselbe Ergebnis.
Die Gleichverteilung ist eine zusätzliche Voraussetzung und folgt nicht aus der Anzahl allein. Ein Verfahren, das eine bestimmte Person immer einbezieht, macht nicht alle 56 Teams gleich wahrscheinlich. Werden dagegen nacheinander drei verschiedene Personen jeweils gleichwahrscheinlich gezogen, hat jedes Team sechs gleichwahrscheinliche Auswahlfolgen. Dadurch entstehen gleichwahrscheinliche Teams. Bei unterschiedlichen Gewichten oder Auswahlregeln brauchst du das tatsächliche Zufallsmodell. Reines Abzählen kann fehlende Angaben über Wahrscheinlichkeiten nicht ersetzen und darf sie auch nicht stillschweigend erfinden.
Übertrage den Gedanken auf sieben Personen
Wähle ohne Blick auf das vorige Beispiel ein Zweierteam aus sieben verschiedenen Menschen. Ohne Rollen und Wiederholung erhältst du C(7,2) = 7 × 6 / 2 = 21. Für zwei benannte Rollen gibt es 42 Verteilungen. Erkläre den Faktor zwei durch Vertauschen der beiden gewählten Personen. Sind zwei Menschen zertifiziert und fünf nicht, gibt es mit genau einer zertifizierten Person C(2,1)C(5,1) = 10 Teams. Mindestens eine zertifizierte Person ergibt 21 − C(5,2) = 11 Teams.
Das zusätzlich zulässige zertifizierte Paar erklärt den Unterschied zwischen zehn und elf. In einem kleinen Fall kannst du vollständig auflisten: Für vier Personen sind AB, AC, AD, BC, BD und CD die sechs Zweierteams. Verdoppelt sich deine Liste beim Umdrehen der Namen, prüfe erneut, was ein Ergebnis bedeutet. Formuliere zum Schluss Grundmenge, Auswahlgröße, Rollen, Wiederholungsregel und Nebenbedingungen in einem Satz. Diese Beschreibung begründet die gewählte Formel besser als ein alleinstehendes Rechnerkürzel.
