Fall 1
- Elementtypen (n)
- 5
- Gewählte Elemente (r)
- 3
35
Mit diesen Werten öffnenKombinationen mit Wiederholung
35Auswahlen
Ergebnis: 35 AuswahlenDrei Kugeln aus fünf Eissorten, Doppelte erlaubt, Reihenfolge egal: C(5 + 3 − 1, 3) = C(7, 3) = 35 Auswahlen. Ohne Wiederholung hätte dieselbe Frage nur 10 Antworten. Weil Wiederholungen erlaubt sind, darf r größer als n sein — fünf Kugeln aus zwei Sorten ergibt sechs Antworten.
Die Zahlen auf einen Blick
Festgehalten: Elementtypen (n) 5.
| Gewählte Elemente (r) | Ergebnis |
|---|---|
| 1 | 5 |
| 2 | 15 |
| 3Dein Wert | 35 |
| 4 | 70 |
| 5 | 126 |
Beispiele durchgerechnet
Fall 2
- Elementtypen (n)
- 10
- Gewählte Elemente (r)
- 2
55
Mit diesen Werten öffnenFall 3
- Elementtypen (n)
- 6
- Gewählte Elemente (r)
- 6
462
Mit diesen Werten öffnenSo wird gerechnet
C(n + r − 1, r)
- SchrittAls n eintragen, aus wie vielen verschiedenen Typen du schöpfst — fünf Sorten, drei Münzwerte.
- SchrittAls r eintragen, wie viele du insgesamt nimmst; Doppelte sind erlaubt, die Reihenfolge zählt nicht.
- ErgebnisDie Zahl der verschiedenen Körbe ablesen — jeder Korb zählt einmal, egal wie er zustande kam.
Was die Zahl bedeutet
Das ist die Zählfrage, bei der nichts verbraucht wird: r Griffe aus n Typen, jeder Typ so oft verfügbar wie gewünscht, und ein Korb zählt nur nach seinem Inhalt. Solche Körbe direkt aufzuzählen ist unhandlich, weil ein Korb keine natürliche Reihenfolge hat, an der man sich entlanghangeln könnte. Der Kniff mit Sternen und Strichen übersetzt die Frage in eine leichte. Schreibe einen Korb als Reihe: ein Stern je genommenem Element, dazu n − 1 Striche als Zäune zwischen den n Typen, sodass alles links vom ersten Strich zum ersten Typ gehört und so weiter. Drei Kugeln aus fünf Sorten werden so zu einer Reihe aus drei Sternen und vier Strichen. Jede solche Reihe ist genau ein Korb und jeder Korb genau eine Reihe — zu zählen sind also die Reihen. Eine Reihe hat 3 + 4 = 7 Plätze, und welche 3 davon Sterne tragen, legt sie vollständig fest: C(7, 3) = 35. Allgemein hat die Reihe n + r − 1 Plätze, und heraus kommt C(n + r − 1, r). Zweierlei sagt diese Zahl nicht. Sie setzt unbegrenzten Vorrat jedes Typs voraus — ist eine Sorte auf eine Kugel begrenzt, zählt sie zu hoch. Und gleich viele Körbe sind keine gleich wahrscheinlichen Körbe: Wer wirklich zufällig greift, landet weit öfter bei gemischten Körben als bei drei gleichen.
Reihenfolge egal, aber eine Sorte darf doppelt
Du schöpfst aus unbegrenztem Vorrat jedes Typs, und jeder Korb zählt einmal, egal wie er zustande kam. Drei Kugeln aus fünf Sorten: C(5 + 3 − 1, 3) = C(7, 3) = 35 Körbe.
Es wächst, obwohl die Reihenfolge egal ist
Erlaubte Doppelungen bringen zusätzliche Körbe, nicht zusätzliche Reihenfolgen: drei aus fünf Typen ergibt 10 gewöhnliche Kombinationen, mit Wiederholung aber 35. Weil nichts verbraucht wird, darf r auch größer als n sein — fünf Kugeln aus zwei Sorten ergeben sechs Antworten.
Sterne und Striche liefern die Formel
Lege r gleiche Sterne in n beschriftete Kästen; zum Trennen der Kästen brauchst du n − 1 Striche. Jede Reihe aus r Sternen und n − 1 Strichen ist genau eine Auswahl, und davon gibt es C(n + r − 1, r).
Häufig falsch verstanden
Drei Kugeln aus fünf Sorten sind C(5, 3) = 10.
Diese Antwort verbietet, eine Sorte zweimal zu nehmen. Mit erlaubten Doppelungen sind es C(7, 3) = 35.
Schokolade, Vanille, Schokolade und Vanille, Schokolade, Schokolade sind zwei Auswahlen.
Es sind zwei Folgen, aber derselbe Korb — und dieser Rechner zählt Körbe. Wer die Folgen zählt, landet bei n hoch r und damit weit höher.
Münzwechsel aus drei Werten braucht gewöhnliche Kombinationen.
Jeder Wert lässt sich immer wieder verwenden, also gehört die Frage hierher. Die gewöhnliche Form passt zu einzelnen Gegenständen, diese hier zu Typen.
Referenztabelle
| n, r | Gelesen als | Auswahlen |
|---|---|---|
| 4, 0 | gar nichts nehmen | 1 |
| 1, 5 | eine Sorte, fünf Kugeln | 1 |
| 3, 2 | zwei Kugeln aus drei Sorten | 6 |
| 2, 5 | fünf Kugeln aus zwei Sorten | 6 |
| 4, 3 | drei aus vier Typen | 20 |
| 5, 3 | drei Kugeln aus fünf Sorten | 35 |
| 10, 2 | zwei aus zehn Typen | 55 |
| 6, 6 | sechs aus sechs Typen | 462 |
Fragen
Was sind Kombinationen mit Wiederholung?
Sie zählen die Möglichkeiten, r Elemente aus n verschiedenen Typen zu wählen, wenn derselbe Typ mehrfach vorkommen darf und die Reihenfolge keine Rolle spielt. Die Anzahl ist der Multiset-Koeffizient C(n + r − 1, r). Drei Kugeln aus fünf Sorten ergeben C(7, 3), also 35.
Wie unterscheidet sich das von gewöhnlichen Kombinationen?
Gewöhnliche Kombinationen verbrauchen jedes Element, deshalb kann r dort nie größer als n sein; hier schöpfst du aus unbegrenztem Vorrat jedes Typs, r ist also frei. Das Ergebnis ist immer mindestens so groß: drei aus fünf Typen ergibt 10 gewöhnliche Kombinationen, aber 35 mit Wiederholung. Nimm die gewöhnliche Form für einzelne Gegenstände, diese hier für Typen.
Was unterscheidet sie von Permutationen mit Wiederholung?
Beide erlauben denselben Typ zweimal, aber Permutationen zählen geordnete Folgen und Kombinationen ungeordnete Körbe. Schokolade, Vanille, Schokolade ist eine andere Folge als Vanille, Schokolade, Schokolade — und doch derselbe Korb. Permutationen ergeben n hoch r und damit weit mehr.
Was ist die Sterne-und-Striche-Methode?
Lege r gleiche Sterne in n beschriftete Kästen; um die Kästen zu trennen, brauchst du n − 1 Striche. Jede Reihe aus r Sternen und n − 1 Strichen ist genau eine Auswahl, und davon gibt es C(n + r − 1, r). Aus diesem Argument stammt die Formel.
Wo braucht man das?
Überall, wo ein Korb aus unbegrenztem Vorrat zusammengestellt wird, ohne dass die Reihenfolge zählt: Eiskugeln, Pizzabeläge mit erlaubten Doppelungen, Münzwechsel aus gegebenen Werten, Stichproben mit Zurücklegen. Dieselben Koeffizienten tauchen in multivariaten Polynomentwicklungen auf.
Quellen und letzte Prüfung
Information, keine Fachberatung.