Anzahl mögliche Gewichtssätze

27.04.2005, 21:46	matz	Auf diesen Beitrag antworten »
Anzahl mögliche Gewichtssätze Hallo miteinander Ich suche eine Formel für die Anzahl möglicher Gewichte $\begin{eqnarray} w_{i}>0\; , i= 1 ... k \end{eqnarray}$ mit $\begin{eqnarray} \sum_{i=1}^k~w_{i} = 1 \end{eqnarray}$ , wobei nur n äquidistante diskrete Werte zwischen 0 und 1 für die $\begin{eqnarray} w_{i} \end{eqnarray}$ zulässig sein sollen. Ich brauche solche Gewichtssätze für eine Simulation und muss unbedingt wissen, ob ich alle möglichen erwischt habe. Als Beispiel wähle ich die $\begin{eqnarray} w_{i} \end{eqnarray}$ aus $\begin{eqnarray} S=\{0\;0.1\;0.2\; ... 0.9\;1\} \end{eqnarray}$ , d.h. n=11 und k=5 z.B. Schon herausgefunden habe ich, dass es für k=2 genau n Möglichkeiten gibt, da ich das erste Gewicht frei wählen kann und sich das zweite dann aus der Bedingung ergibt, dass die Summe 1 ist. Für k=3 gibt es $\begin{eqnarray} \frac{n(n + 1)}{2} \end{eqnarray}$ Möglichkeiten. Falls ich für das erste Gewicht 0 wähle, dann ist das zweite frei wählbar und das dritte ist dann auch bestimmt (n Möglichkeiten). Falls ich das für das erste Gewicht, das Nächstgrössere wähle verbleiben n-1 Möglichkeiten für das zweite usw. Daraus ergibt sich dann die Formel oben. Für k>3 krieg ichs nicht mehr auf die Reihe mit meinem Ansatz. Ich hoffe, jemand kann mir helfen.
28.04.2005, 07:23	AD	Auf diesen Beitrag antworten »
RE: Anzahl mögliche Gewichtssätze n Gewichtseinheiten sind zu vergeben, auf k mögliche Gewichte - also Auswahlen (Kombinationen) von n aus k Elementen mit Wiederholung. Wiederholung heißt hier, dass pro Gewicht natürlich auch mehr als eine Gewichtseinheit zugeordnet werden kann.
28.04.2005, 09:02	matz	Auf diesen Beitrag antworten »
RE: Anzahl mögliche Gewichtssätze Wenn ich n Gewichtseinheiten frei auf k Gewichte verteile, dann sollte das $\begin{eqnarray} n^{k} \end{eqnarray}$ Möglichkeiten geben, oder ? Das Problem ist doch aber, dass die Summe der Gewichte 1 geben muss. Ich habe auch versucht, die n Gewichtseinheiten einfach auf (k-1) Gewichte zu verteilen, da sich das k-te aus obiger Bedingung ergibt. Das wären dann $\begin{eqnarray} n^{k-1} \end{eqnarray}$ . Dies ist aber leider auch falsch, da ja das k-te Gewicht nicht negativ werden darf, und somit nicht beliebig ist. Also nochmals von vorn, ich glaube ich habe jetzt verstanden. Ich verteile einfach die kleinste Gewichtseinheit (0.1 im Beispiel) auf k Gewichte, wobei ich das n-mal (bzw. n-1 mal nach obiger Definition) mache. Somit ist die Summe der Gewichte immer eins. Die Anzahl Möglichkeiten beträgt somit n+k-1 tief n. Im Beispiel 10+5-1 tief 10 ergibt 14 tief 10 also 1001. Richtig so ?
28.04.2005, 10:19	AD	Auf diesen Beitrag antworten »
Kombinationen, nicht Variationen! Für die genaue Berechnung müssen wir aber zunächst mal klären, was deine unklare Formulierung "n equidistante Gewichte zwischen 0 und 1" bedeuten soll: Soll das heißen Gewichte $\begin{eqnarray} \frac{1}{n+1},\ldots,\frac{n}{n+1} \end{eqnarray}$ , oder doch $\begin{eqnarray} \frac{1}{n},\ldots,\frac{n-1}{n},1 \end{eqnarray}$ ? EDIT: Hat sich erledigt, du hast ja das Beispiel n=11 angebracht. Also meinst du sogar die n Gewichte $\begin{eqnarray} 0,\frac{1}{n-1},\ldots,\frac{n-2}{n-1},1 \end{eqnarray}$ Anders mit natürlichen Zahlen $\begin{eqnarray} a_i:=(n-1)w_i \end{eqnarray}$ ausgedrückt: Du suchst die Anzahl aller geordneten Partitionen $\begin{eqnarray} a_1,\ldots,a_k \end{eqnarray}$ der Zahl $\begin{eqnarray} n-1 \end{eqnarray}$ , also mit der Eigenschaft $\begin{eqnarray} n-1=a_1+\ldots+a_k \end{eqnarray}$ . Nun gibt es aber noch zwei Interpretationsmöglichkeiten: 1.) $\begin{eqnarray} w_i \end{eqnarray}$ (und damit $\begin{eqnarray} a_i \end{eqnarray}$ ) nichtnegativ: Die gesuchte Anzahl ergibt sich als Kombinationen von (n-1) Elementen aus k möglichen Elementen: $\begin{eqnarray} {n-1+k-1\choose n-1}={n+k-2\choose n-1}={n+k-2\choose k-1} \end{eqnarray}$ Für k=2 ergibt sich einfach $\begin{eqnarray} n \end{eqnarray}$ , für k=3 dann $\begin{eqnarray} \frac{n(n+1)}{2} \end{eqnarray}$ , also deine Resultate. 2.) $\begin{eqnarray} w_i \end{eqnarray}$ (und damit $\begin{eqnarray} a_i \end{eqnarray}$ ) positiv: Hier rechnet man die Anzahl über Kombinationen von (n-1-k) Elementen aus k möglichen Elementen aus, da ja jedes der k Gewichte mindestens 1 sein muss: $\begin{eqnarray} {n-1-k+k-1\choose n-1-k}={n-2\choose n-1-k}={n-2\choose k-1} \end{eqnarray}$ Für k=2 ergäbe sich hier $\begin{eqnarray} n-2 \end{eqnarray}$ , für k=3 dann $\begin{eqnarray} \frac{(n-2)(n-3)}{2} \end{eqnarray}$ . Sieht also ganz danach aus, als meinst du nichtnegative Gewichte, obwohl du oben deutlich ( $\begin{eqnarray} w_i>0 \end{eqnarray}$ ) von positiven Gewichten gesprochen hast. Da musst du dir wohl noch mit dir selbst einig werden.
28.04.2005, 20:38	matz	Auf diesen Beitrag antworten »
Danke Arthur Dent, Problem ist gelöst. Wie du richtig sagst, meine ich nichtnegative Gewichte (null ist erlaubt). Allerdings habe ich das in meinem Beispiel auch so dargestellt. Die Bedingung sollte korrekt $\begin{eqnarray} w_{i} \geq 0 \end{eqnarray}$ heissen.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »