Die Kombinatorik zählt Möglichkeiten, ohne sie alle einzeln aufzulisten. Entscheidend ist, wodurch sich zwei Ergebnisse unterscheiden: durch ihre Reihenfolge, durch die ausgewählten Elemente oder durch beides. Zusätzlich muss feststehen, ob Wiederholungen erlaubt sind.
Die Produktregel beim Zählen
Ein Geschäft bietet drei Schuhmodelle in jeweils zwei Farben an. Modell und Farbe lassen sich auf 3 × 2 = 6 Arten wählen. Die Anzahlen der Möglichkeiten in den einzelnen Schritten werden multipliziert. Schränkt eine Wahl spätere Schritte ein, zählt dort nur die tatsächlich verbleibende Auswahl.
Was bedeutet die Fakultät?
Die Fakultät einer positiven ganzen Zahl ist das Produkt dieser Zahl mit allen kleineren positiven ganzen Zahlen. Die Fakultät von null ist als eins festgelegt. Das passt zur einzigen Möglichkeit, eine leere Auswahl anzuordnen.
Alle Elemente anordnen
Für n verschiedene Elemente auf n Plätzen gibt es zunächst n Möglichkeiten, dann n − 1 und so weiter. Drei Kandidaten können ohne Gleichstand sechs verschiedene Platzierungsreihenfolgen bilden.
Sind Elemente gleich, erzeugt ihr Vertauschen keine neue Anordnung. Deshalb wird durch die Fakultät jeder Wiederholungsanzahl geteilt. ANNA enthält vier Buchstaben mit zwei A und zwei N und besitzt sechs verschiedene Buchstabenanordnungen.
Variationen: Die Reihenfolge zählt
Aus {1, 2, 3, 5, 7, 9} dreistellige Zahlen ohne Ziffernwiederholung zu bilden, ist eine geordnete Auswahl. 123 und 321 sind verschieden. Deshalb gibt es 6 × 5 × 4 = 120 Zahlen.
Mit Wiederholung stehen für jede Stelle wieder alle n Optionen zur Verfügung. Zwei Stellen aus den fünf Buchstaben A, E, I, O und U ergeben 25 Folgen, darunter AA und AE.
Kombinationen: Nur die Auswahl zählt
Drei verschiedene Murmeln aus zwölf auszuwählen, ergibt 220 Gruppen. Gemeint ist eine einzelne Dreiergruppe, nicht die Aufteilung aller zwölf Murmeln auf mehrere Gefäße. Die verschiedenen Reihenfolgen innerhalb derselben Gruppe zählen nur einmal.
Warum drei Murmeln aus zwölf genau 220 Gruppen ergeben
Zwölf Murmeln sind verschieden, und wir wählen drei ohne Zurücklegen. Eine andere Reihenfolge derselben drei Murmeln ergibt keine neue Gruppe. Deshalb verwenden wir eine Kombination mit n = 12 und k = 3.
Setze die Anzahlen in die Formel ein. Wegen 12 − 3 = 9 steht als zweite Fakultät im Nenner die Fakultät von 9.
Kürze die gemeinsame Fakultät von 9. Die drei verbleibenden Faktoren im Zähler zählen geordnete Auswahlen; der Nenner entfernt die sechs Reihenfolgen jeder Gruppe.
Berechne Zähler und Nenner und dividiere. Jede ungeordnete Gruppe wird jetzt genau einmal gezählt.
Es gibt 220 Auswahlen. Multipliziert mit den sechs inneren Reihenfolgen ergeben sie 1.320 geordnete Auswahlen und bestätigen die Ausgangszählung.
Auswählen mit Wiederholung
Wer drei Paar Schuhe aus zehn Marken auswählt, Marken mehrfach wählen darf und die Reihenfolge ignoriert, hat 220 Markenauswahlen. Vorausgesetzt werden ausreichende Verfügbarkeit und eine Unterscheidung ausschließlich nach Marke.
Dabei bezeichnet n die Zahl verfügbarer Elemente oder Arten und k die Zahl der gewählten Elemente. Ohne Wiederholung darf k nicht größer als n sein. Vergleiche AB und BA: Sind sie dasselbe Ergebnis? Prüfe anschließend, ob AA erlaubt ist. Diese beiden Entscheidungen legen die Zählmethode fest.
