Binomialkoeffizient/ Auswählen von k aus n Elementen

01.03.2016, 16:44	alina94	Auf diesen Beitrag antworten »
Binomialkoeffizient/ Auswählen von k aus n Elementen Hey Ich arbeite mich grade durch mein Diskrete Mathematik Skript und hab hier eine Formel bei der ich nicht weiter weiß. Wir haben zuerst die geordnete Summation definiert durch $\begin{eqnarray} \left(X_{n,k}\right) = \left\{\left(s_{1},...,s_{k} \right) \in \mathbb N^{k} :s_{1}+...+s_{k} = n \right\} \end{eqnarray}$ und gezeigt, dass $\begin{eqnarray} \|X_{n,k}\| = \begin{pmatrix} n+k-1 \\ k-1 \end{pmatrix} \end{eqnarray}$ . Dazu haben wir das $\begin{eqnarray} n \end{eqnarray}$ als $\begin{eqnarray} n \end{eqnarray}$ Symbole dargestellt die durch $\begin{eqnarray} k-1 \end{eqnarray}$ trennungsstriche in $\begin{eqnarray} k \end{eqnarray}$ Teile aufgeteilt wurden. Insgesamt gab es also $\begin{eqnarray} n+k-1 \end{eqnarray}$ Symbole und dementsprechend $\begin{eqnarray} \begin{pmatrix} n+k-1 \\ k-1 \end{pmatrix} \end{eqnarray}$ Möglichkeiten, die $\begin{eqnarray} k-1 \end{eqnarray}$ Trennungssymbole zu verteilen, also insgesamt auch $\begin{eqnarray} \begin{pmatrix} n+k-1 \\ k-1 \end{pmatrix} \end{eqnarray}$ Möglichkeiten für diese Summationen, finde ich logisch soweit. Später hatten wir dann allerdings zum Auswählen von $\begin{eqnarray} k \end{eqnarray}$ aus $\begin{eqnarray} n \end{eqnarray}$ Elementen, ungeordnet und mit Zurücklegen, die Formel $\begin{eqnarray} \begin{pmatrix} n+k-1 \\ k \end{pmatrix} \end{eqnarray}$ und dabei wurde auf die Formel für die Anzahl der ungeordneten Summationen verwiesen. Laut Internet ist die 2. Formel die Richtige, aber ich verstehe nicht wieso. Was ist mit dem $\begin{eqnarray} k \end{eqnarray}$ passiert? Oder sind beide Formeln richtig und die 2. musste für den anderen Fall nur etwas angepasst werden? Danke schon mal im Voraus! e.: Sorry falls ich im falschen Bereich bin, könnte auch in Sonstiges gehören aber ich dachte Kombinatorik wird schon richtig sein.
01.03.2016, 17:08	HAL 9000	Auf diesen Beitrag antworten »
Beide Formeln sind richtig, in ihrem jeweiligen Kontext: Deine erste Variante kann man interpretieren als Ziehen von $\begin{align} n \end{align}$ aus $\begin{align} k \end{align}$ Elementen mit Zurücklegen, d.h., die Rollen der beiden Parameter $\begin{align} n,k \end{align}$ sind vertauscht gegenüber der zweiten Variante. Gemäß der zweiten Formel (unter Berücksichtigung der vertauschten Rollen) ergibt das Anzahl $\begin{align} \binom{k+n-1}{n} = \binom{n+k-1}{n} \stackrel{!}{=} \binom{n+k-1}{(n+k-1)-n} = \binom{n+k-1}{k-1} \end{align}$ , also genau die Formel vom Anfang. (Beim $\begin{align} \stackrel{!}{=} \end{align}$ wird die bekannte Symmetrie $\begin{align} \binom{u}{v} = \binom{u}{u-v} \end{align}$ des Binomialkoeffizienten genutzt.) Verwirrt? Kann ich verstehen, lass es dir nochmal ganz ruhig durch den Kopf gehen - vor allem versuche zu verstehen, warum die Ausgangssituation als "Ziehen von $\begin{align} n \end{align}$ aus $\begin{align} k \end{align}$ Elementen mit Zurücklegen" verstanden werden kann. P.S.: Bereich "Kombinatorik" ist vollkommen richtig.
01.03.2016, 20:04	alina94	Auf diesen Beitrag antworten »
Ah so langsam wird es mir klar. Vielen Dank für die Antwort, hat mir sehr geholfen

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »