Kombinatorik-Problem

17/10/2007 - 10:49 von hauke.krueger | Report spam
Hallo zusammen,

ich habe folgendes Problem, für das ich keine Lösung finde:

Ich definiere N Behàlter Xn mit X1, X2, ... , XN.
In jedem Behàlter sind LXn freie Plàtze für Bàlle.

Mein Ziel ist es nun, L Bàlle auf die N Behàlter aufzuteilen.

Beipiel:

Gegeben seien 3 Behàlter X1, X2 und X3. In Behàlter X1 passen LX1=2
Bàlle, in
Behàlter X2 LX2=3 Bàlle und in Behàlter X3 LX3=2 Bàlle.
Ingesamt L=5 Bàlle werden nun auf die drei Behàlter verteilt, möglich sind

X1 X2 X3

0 3 2
1 2 2
1 3 1
2 1 2
2 2 1
2 3 0

Meine Frage ist nun: Ist jemandem eine Formel bekannt, um die Anzahl der
möglichen
Kombinationen von Ballverteilungen (im Beispiel 6) auszurechnen?
Ich kann wohl einen rekursiven Algorithmus dafür schreiben, aber
eine geschlossene Lösung wàre besser.

Vielen Dank und viele Grüße,

Hauke
 

Lesen sie die antworten

#1 Jan Fricke
18/10/2007 - 11:05 | Warnen spam
hauke.krueger wrote:
Ich definiere N Behàlter Xn mit X1, X2, ... , XN.
In jedem Behàlter sind LXn freie Plàtze für Bàlle.

Mein Ziel ist es nun, L Bàlle auf die N Behàlter aufzuteilen.



[Beispiel herausgelassen]

Meine Frage ist nun: Ist jemandem eine Formel bekannt, um die Anzahl der
möglichen
Kombinationen von Ballverteilungen (im Beispiel 6) auszurechnen?
Ich kann wohl einen rekursiven Algorithmus dafür schreiben, aber
eine geschlossene Lösung wàre besser.



Es wird wahrscheinlich keine geschlossene Formel geben, es sei denn, Du
hast spezielle Konfigurationen.
Möglicherweise ist für Dich noch interessant, dass man die Anzahlen auch
mit erzeugenden Polynomen berechnen kann. Dazu setzt man:
p_n(x) = x^0 + x^1 + ... + x^(LXn).
Das Produktpolynom
P(x) = p_1(x) * ... * p_N(x)
hat jetzt folgende interessante Eigenschaft: Der Koeffizient vor x^L
gibt die Anzahl der Möglichkeiten an, L Bàlle in der gewünschten Art und
Weise auf die N Behàlter zu verteilen. (Zum Beweis klammere man das
Produkt aus. Dann sieht man, dass jede Verteilungsmöglichkeiten einen
Summanden x^L liefert.) Bei Deinem Beispiel hàtte man:
P(x) = (1+x+x²) * (1+x+x²+x³) * (1+x+x²)
= 1 + 3x + 6x² + 8x³ + 8x^4 + 6x^5 + 3x^6 + x^7.
Für L=5 liest man als Ergebnis 6 ab.

Viele Grüße Jan

Ähnliche fragen