Kombination mit Wiederholung! < Kombinatorik < Stochastik < Hochschule < Mathe < Vorhilfe
|
Guten Tag.
Habe ein kleines Verständnisproblem mit einer Formel aus der Kombinatorik! Die Formeln für Permutation Variation und Kombination verstehe ich alle außer der Kombination mit Wiederholung.
Sie lautet wie folgt: (n+k-1)/(n-1)!*k!
Kann mir jemdand human erläutern, wie es zu dieser Formel kommt?
Ich bedanke mich schon einmal im Vorraus
Mfg Jan
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:55 Mi 17.10.2007 | | Autor: | statler |
Hi Jan, ![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]")
> Habe ein kleines Verständnisproblem mit einer Formel aus
> der Kombinatorik! Die Formeln für Permutation Variation und
> Kombination verstehe ich alle außer der Kombination mit
> Wiederholung.
> Sie lautet wie folgt: (n+k-1)!/(n-1)!*k!
> Kann mir jemand human erläutern, wie es zu dieser Formel
> kommt?
Nicht zufällig wird diese Formel in der Schule meistens nicht angewendet. Wenn du die Formel für k-mal Ziehen ohne Zurücklegen kennst, dann kannst du dir diese wie folgt herleiten: Für die n verschiedenen Kugeln machst du dir n Plätze, die du durch n-1 Striche trennst. Für jede gezogene Kugel machst du ein Kreuz an ihrem Platz. Wenn n = 10, k = 4 ist und du die 1, 2mal die 3 und die 9 gezogen hast, sieht das so aus:
x||xx||||||x|
Damit ist dein Ergebnis festgelegt, du kannst also k Objekte (Kreuze) irgendwie auf n-1+k Plätze packen. Die restlichen Plätze werden dann von Strichen belegt. Für diesen Vorgang hast du die Formel ohne Zurücklegen.
So verständlich?
Gruß aus HH-Harburg
Dieter
|
|
|
| |
|
mhh.. also erstmal dankeschön für Ihre Antwort!
MIr ist klar, dass die Formel n!/(n-k)! die Variation mit Reihenfolge angibt, weil der Faktor k! weggelassen wurden ist und man durch (n-k)! teilt, weil es sich um eine bestimmte anzahl von Ziehungen handelt. Unklar ist mir jetzt, wieso man für die Kombination ohne Reihenfolge ( also mit k! unter dem Bruch) im Zähler diese so genannten Tennzeichen x einfügt. Das muss ja etwas damit zu tun haben, dass die Ausgangsmenge immer gleich bleibt oder liege ich da falsch? Wäre nett wenn Sie mir dies noch etwas genauer erläutern könnten.
Mfg Jan
|
|
|
| |
|
Es handelt sich hier um den Typ "Zigaretten holen". Beispiel: Hole 12 Packungen Zigaretten, wobei im Automaten 5 verschiedene Sorten sind.
Wieviel Möglichkeiten hast du?
Natürlich kommt es nun nicht darauf an, ob du zuerst eine Packung von Sorte 1 und dann 3 von Sorte 2 ziehst oder zuerst 3 von Sorte 2 und dann eine von Sorte 1, sondern welche Zusammenstellungen möglich sind.
Wie gehst du systematisch vor? Du schreibst alle Möglichkeiten auf für die Anzahl von Sorte 1, Sorte 2 ... Sorte 5, wobei die Summe immer 12 ergeben muss. Du darfst keine Kombination doppelt haben und keine auslassen.
Am einfachsten geht das nun so: Du nimmst im Heft 12 Kästchen für die Schachteln und 4 (nicht 5) Trennkästchen (wird unten verständlicher) zwischen den Sorten, also 12+(5-1) Kästchen.
Für 4 Trennkästchen besorgst du dir 4 Kreuze. Damit kannst du nun alle möglichen Kombinationen darstellen. Ich wähle als normales Kästchen das Zeichen [mm] \Box [/mm] und für das Kästchen mit Trennzeichen ein [mm] \otimes. [/mm]
Beispiel:
[mm] \Box\Box\Box\otimes\otimes\Box\Box\Box\otimes\Box\Box\Box\Box\Box\Box\otimes
[/mm]
bedeutet nun:
Sorte 1 1 1 [mm] \otimes\otimes3 [/mm] 3 3 [mm] \otimes [/mm] 4 4 4 4 4 4 [mm] \otimes [/mm] ,
also 3 Schachteln von Sorte 1, dann kommt das Trennkästchen zu Sorte 2, dann sofort das zu Sorte 3, also haben wir Sorte 2 gar nicht gewählt, dann 3 Schachteln Sorte 3 und nach dem nächsten Kästchen 6 Schachteln Sorte 4. Nach dem Trennkästchen zu Sorte 5 ist kein Feld mehr übrig, weil wir schon 12 Schachteln haben.
Wenn du also auf irgendeine Weise die 4 Trennkästchen in die 16 Felder setzt, bleiben immer 12 Kästchen für die Anzahl der jeweiligen Zigarettensorten-Packungen frei. Die Sorte selber ergibt sich durch "Überschreiten" der Trennkästchen. Sind z.B. die ersten 4 Kästchen [mm] \otimes, [/mm] so hast du nur Sorte 5 gekauft.
Nun wird klar:
Jede Möglichkeit, die Trennkästchen aus den 16 Kästchen auszuwählen, bedeutet eine andere Kombination.
Jede mögliche Kombination lässt sich durch genau eine eindeutige Lage der Trennkästchen darstellen.
Also gibt es genau so viele Möglichkeiten, wie es "Trennkästchen-Bilder" gibt.
Da du für die Trennkästchen aber einfach nur 4 aus 16 (allgemein: k-1 aus n+ k-1) Kästchen auswählen musst, wobei die Reihenfolge der Auswahl ja keine Rolle spielt, gibt es [mm] \vektor{1 \\ 4} [/mm] oder allgemein [mm] \vektor{n+k-1 \\ k-1} [/mm] Möglichkeiten.
|
|
|
|
