Bestimmen der Anzahl der Möglichkeiten (Kombinatorik mit Abbruchbedingung)

13.08.2013, 09:15

Wolfgang Issbegierig

Bestimmen der Anzahl der Möglichkeiten (Kombinatorik mit Abbruchbedingung)

Meine Frage:

Ich habe eine Menge von Vektoren ( $\begin{eqnarray*} V=\left\{ v_{1}, v_{2}, v_{3},...v_{n}\right\} <br /> \end{eqnarray*}$ ) deren Elemente jeweils mit einem Gewicht $\begin{eqnarray*} g_{x} \end{eqnarray*}$ mit $\begin{eqnarray*} x<g\wedge g\in \mathbb N <br /> \end{eqnarray*}$ belegt werden soll. Wobei $\begin{eqnarray*} g_{x}\in G \wedge G = \left\{\frac{0}{g}, \frac{1}{g}, \frac{2}{g},...\frac{g}{g} \right\} \end{eqnarray*}$ . Die Summe der Gewichtung der Vektoren muss 1 entsprechen.

Wie viele Möglichkeiten gibt es abhängig von $\begin{eqnarray*} n \end{eqnarray*}$ und $\begin{eqnarray*} g \end{eqnarray*}$ ?

Meine Ideen:
Ich habe ursprünglich das Urnenmodell versucht anzuwenden. Jedoch hat weder die Ziehung in geordneter Reihenfolge (mit oder ohne Zurücklegen), noch die ungeordnete Ziehung ( mit oder ohne Zurücklegen) mir das Erhoffte Ergebnis gebracht. Auch die anschauliche Analyse der Anzahl der Möglichkeiten für kleine Beispiele (n=3, g=1 bis 5)hat nicht nicht nennenswert weiter gebracht. Ich bin für jeden Tip dankbar.

13.08.2013, 09:26

HAL 9000

Auf diesen Beitrag antworten »

Das läuft letztendlich auf die kombinatorische Frage hinaus, wieviele n-Tupel $\begin{eqnarray*} (x_1,\ldots,x_n) \end{eqnarray*}$ nichtnegativer ganzer Zahlen es gibt, für die

$\begin{eqnarray*} x_1+\ldots+x_n = g \end{eqnarray*}$

gilt. Die Antwort liefern Kombinatione
n mit Wiederholung:

$\begin{eqnarray*} \binom{n+g-1}{g} = \binom{n+g-1}{n-1} \end{eqnarray*}$

Zitat:

Original von Wolfgang Issbegierig
Jedoch hat weder die Ziehung in geordneter Reihenfolge (mit oder ohne Zurücklegen), noch die ungeordnete Ziehung ( mit oder ohne Zurücklegen) mir das Erhoffte Ergebnis gebracht.

Eigentlich doch, wie man oben sieht.

13.08.2013, 10:26

Wolfgang Issbegierig

Auf diesen Beitrag antworten »

Das dachte ich bis vor ein paar Wochen auch. Aber beim überarbeiten meiner Aufzeichnungen habe ich Zahlenbeispiele genutzt und stieß auf folgendes Beispiel.

Wenn ich 3 Vektoren nutze (n=3) und (g=1) ergibt das laut der Formel für Kombinationen mit Wiederholung:

$\begin{eqnarray*} \binom{n+g-1}{g} = \binom{3+1-1}{3} = \binom{3}{3} = 1 \end{eqnarray*}$

Es gibt jedoch 3 Möglichkeiten:

Menge der Möglichkeiten = $\begin{eqnarray*} \left\{\left(1,0,0\right),\left(0,1,0\right),\left(0,0,1\right) \right\} \end{eqnarray*}$

Anschließend dachte ich: Ja klar die Reihenfolge ist doch relevant.

Also versuchte ich dich Formel für die Variation mit Wiederholung:

$\begin{eqnarray*} { g^n }_{} = { 3^1 }_{}=3 \end{eqnarray*}$

Jetzt dachte ich die Lösung gehabt zu haben. Und Prüfte noch für n=3 und g=2:

$\begin{eqnarray*} { g^n }_{} = { 3^2 }_{}=6 \end{eqnarray*}$

Und Prüfte noch für n=3 und g=3:

$\begin{eqnarray*} { g^n }_{} = { 3^3 }_{}=27 \end{eqnarray*}$

Das war dann auch nicht das gewünschte Ergebnis da die Abbruchbedigung, dass die Summe der Gewichte 1 nicht übersteigen darf, nicht berücksichtigt wird. Unter der Bedingung n=3 und g=3 muss das Ergebnis 10 sein. Die Menge der Möglichkeiten sind dann nämlich:

$\begin{eqnarray*} \left\{\left(\frac{3}{3},0,0\right),\left(0,\frac{3}{3},0\right),\left(0,0,\frac{3}{3}\right),\left(\frac{1}{3},\frac{1}{3},\frac{1}{3}\right),\left(0,\frac{1}{3},\frac{2}{3}\right),\left(\frac{1}{3},0,\frac{2}{3}\right),\left(0,\frac{2}{3},\frac{1}{3}\right) ,\left(\frac{2}{3},0,\frac{1}{3}\right),\left(\frac{1}{3},\frac{2}{3},0\right),\left(\frac{2}{3},\frac{1}{3},0\right)\right\} \end{eqnarray*}$

Also ist keine dieser Formeln die richtige, oder mache ich gerade einen enormen Denkfehler?

13.08.2013, 10:30

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Wolfgang Issbegierig
Wenn ich 3 Vektoren nutze (n=3) und (g=1) ergibt das laut der Formel für Kombinationen mit Wiederholung:

$\begin{eqnarray*} \binom{n+g-1}{g} = \binom{3+1-1}{3} = \binom{3}{3} = 1 \end{eqnarray*}$

Falsch eingesetzt: n=3 und g=1 eingesetzt ergibt

$\begin{eqnarray*} \binom{n+g-1}{g} = \binom{3+1-1}{1} = \binom{3}{1} = 3 \end{eqnarray*}$ .

So lange am Beitrag gearbeitet, und dann solche Fehler... unglücklich

13.08.2013, 11:04

Wolfgang Issbegierig

Auf diesen Beitrag antworten »

Oje

Also noch Mal von vorne. Wenn n=3 und g=1 ergibt das laut der Formel für Kombinationen mit Wiederholung:

$\begin{eqnarray*} \binom{n+g-1}{g} = \binom{1+3-1}{1} = \binom{3}{1} = 3 \end{eqnarray*}$ Freude

n=3 und g=2:

$\begin{eqnarray*} \binom{n+g-1}{g} = \binom{2+3-1}{2} = \binom{4}{2} = 6 \end{eqnarray*}$ Freude

n=3 und g=3:

$\begin{eqnarray*} \binom{n+g-1}{g} = \binom{3+3-1}{3} = \binom{5}{3} = 10 \end{eqnarray*}$ Freude

Vielen Dank HAL 9000

13.08.2013, 11:14

HAL 9000

Auf diesen Beitrag antworten »

Dann ist ja gut. Augenzwinkern

Übrigens, falls du hier bei

Zitat:

Original von Wolfgang Issbegierig
$\begin{eqnarray*} g_{x} \end{eqnarray*}$ mit $\begin{eqnarray*} x<g\wedge g\in \mathbb N <br /> \end{eqnarray*}$ belegt werden soll. Wobei $\begin{eqnarray*} g_{x}\in G \wedge G = \left\{\frac{0}{g}, \frac{1}{g}, \frac{2}{g},...\frac{g}{g} \right\} \end{eqnarray*}$ .

mit $\begin{eqnarray*} g_x \end{eqnarray*}$ den Wert $\begin{eqnarray*} g_x=\frac{x}{g} \end{eqnarray*}$ gemeint haben solltest, dann forderst du aber nicht $\begin{eqnarray*} x<g \end{eqnarray*}$ , sondern "nur" $\begin{eqnarray*} x\leq g \end{eqnarray*}$ , d.h. du lässt durchaus den Wert $\begin{eqnarray*} x=g \end{eqnarray*}$ zu. Zumindest legen das deine angeführten Beispiele nahe. Augenzwinkern

13.08.2013, 11:18

Wolfgang Issbegierig

Auf diesen Beitrag antworten »

Danke ja auch da hast du recht.

Freude

Neue Frage »

Antworten »

Bestimmen der Anzahl der Möglichkeiten (Kombinatorik mit Abbruchbedingung)

Verwandte Themen