Kombinatorik: mit Wiederholung ohne Reihenfolge

05.05.2011, 18:31	Loulo	Auf diesen Beitrag antworten »
Kombinatorik: mit Wiederholung ohne Reihenfolge Meine Frage: Hallo zusammen, ich beschäftige mich zur Zeit mit dem Thema Kombinatorik. So weit ist alles klar, ich verstehe die Formeln und deren Herleitung... bis auf eine! Das ist die Formel für "Ziehungen" mit Wiederholung und ohne Reihenfolge. Ich verstehe einfach die ganze Herleitung der Formel nicht... Kann zwar n und k einsetzen und ausrechnen, aber ich möchte ja auch verstehen wie man zu der Formel kommt. Meine Ideen: Wäre nett wenn ihr mir schnell helfen könntet. Ich verstehe das einfach nicht und brauch jemanden der mir das möglichst einfach erklären kann.
06.05.2011, 08:23	BarneyG.	Auf diesen Beitrag antworten »
Es gibt mehrere Möglichkeiten die Formel zu beweisen. Der beste Beweis ist leider ein wenig abstrakt. Aber dafür versteht man auch das Wesen der Formel. Na,mal sehen, ob er dir gefällt: Gegeben sei eine Menge von n Elementen. Wir ordnen jedem der n Elemente eine Ordnungszahl von 1 bis n zu, d.h. wir zählen die Menge einfach ab. Nun wählen wir k Elemente ohne Reihenfolge und mit Zurücklegen aus diesen n Elementen aus. Jedes ausgewählte Element hat eine Ordnungszahl. Da wir die Reihenfolge nicht beachten, können wir die ausgewählten Elemente nach ihrer Ordnungszahl sortieren. Die k ausgewählten Elemente mögen die Ordnungszahlen $\begin{eqnarray} a_1 \end{eqnarray}$ bis $\begin{eqnarray} a_k \end{eqnarray}$ haben: (1) $\begin{eqnarray} 1 \leq a_1 \leq a_2 \leq ... \leq a_k \leq n \end{eqnarray}$ Es gilt das $\begin{eqnarray} \leq \end{eqnarray}$ Zeichen, weil die Elemente ja wiederholt gezogen werden können. Nun erzeugen wir aus dieser Folge $\begin{eqnarray} (a_i) \end{eqnarray}$ eine zweite Folge $\begin{eqnarray} (b_i) \end{eqnarray}$ nach der folgenden Vorschrift: $\begin{eqnarray} (b_1, b_2, ..., b_k) := (a_1, a_2 + 1, a_3 + 2, ..., a_k + k - 1) \end{eqnarray}$ Für diese Folge gilt: (2) $\begin{eqnarray} 1 \leq b_1 < b_2 < ... < b_k \leq n + k - 1 \end{eqnarray}$ Und nun kommt der entscheidende Schluss: Jeder Folge $\begin{eqnarray} (a_i) \end{eqnarray}$ mit der Eigenschaft (1) kann man eine Folge $\begin{eqnarray} (b_i) \end{eqnarray}$ mit der Eigenschaft (2) zuordnen und umgekehrt. Diese Zuordnung ist also bijektiv. Die Anzahl der Folgen mit der Eigenschaft (1) ist damit genauso groß, wie die Anzahl der Folgen mit der Eigenschaft (2). Weil nun das < Zeichen gilt, gibt es nun KEINE Wiederholungen mehr. Es werden also k Elemente aus (n + k -1) Elementen ohne Reihenfolge und OHNE Wiederholung ausgewählt. Die Anzahl der Möglichkeiten für diese Auswahl kann man aber nach der folgenden Formel berechnen: $\begin{eqnarray} \begin{pmatrix} n + k - 1\\ k \end{pmatrix} \end{eqnarray}$ Die Auswahl von k aus n Elementen ohne Reihenfolge mit Zurücklegen ist also gleichwertig zur Auswahl von k aus (n + k - 1) Elementen ohne Reihenfolge ohne Zurücklegen. Und genau darin liegt der Schlüssel zum Verständnis dieser Formel.
06.05.2011, 19:40	Loulo	Auf diesen Beitrag antworten »
Hallo , also erstmal danke für deine Antwort! Ich hätte da aber noch eine Frage... kann man auch die Formel (n+k-1)! durch k!(n-1)! nehmen? Weil bis jetzt habe ich nur einmal von jener gehört und von deiner sonst nur.
06.05.2011, 21:55	BarneyG.	Auf diesen Beitrag antworten »
Na, aber klar doch ... Es gilt bekanntermaßen $\begin{eqnarray} \begin{pmatrix} n \\ k \end{pmatrix} = \frac{n!}{k! (n-k)!} \end{eqnarray}$ Und nun wendest du das auf unsere Formel an: $\begin{eqnarray} \begin{pmatrix} n+k-1 \\ k \end{pmatrix} = \frac{(n+k-1)!}{k! ((n+k-1)-k)!} = \frac{(n+k-1)!}{k! (n-1)!} \end{eqnarray}$

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »