Interessante (?) Frage Kombinatorik

[Michael II]

Das ist ein typischer "Ziehen ohne Zurücklegen" Fall. n Kugeln, d Kugeln ziehen. n tief d Fälle.

Nimm zum Beispiel n=5 nummerierte Kugeln und ziehe aus diesen 2 Kugeln.

Alle Möglichkeiten aus 5 Kugeln 2 auszuwählen (insgesamt 5 tief 2 = 10 Fälle). Die gezogenen Kugeln markieren wir in der Liste mit X:

XX345
X2X45
X23X5
X234X
1XX45
1X3X5
1X34X
12XX5
12X4X
123XX

Die zwei X unterteilen jede gefundene Lösung in 3 Teile.
Wir können die Anzahl der Kugeln pro Teil zählen und in einen Vektor schreiben:

XX345 (0,0,3)
X2X45 (0,1,2)
X23X5 (0,2,1)
X234X (0,3,0)
1XX45 (1,0,2)
1X3X5 (1,1,1)
1X34X (1,2,0)
12XX5 (2,0,1)
12X4X (2,1,0)
123XX (3,0,0)

Die Ziehung 1X34X erzeugt den Vektor (1,2,0): Wir haben in dieser Ziehung die zwei Kugeln 2 und 5 gezogen (durch X markiert). Links von Kugel 2 liegt 1 Kugel (nämlich Kugel 1) [d.h. für unseren Vektor (1,.,.)], links von Kugel 5 liegen die 2 Kugeln 34 [d.h. (.,2,.)] und rechts von Kugel 5 liegt keine Kugel [(.,.,0)].


Wir haben mit diesem Beispiel den Fall "Wir wollen Vektoren mit 3 Elementen, die Summe der Vektorelemente soll 3 ergeben" gelöst.

Allgemein:

Du benötigst einen Vektor (x1,x2,x3,x4....xv) bestehend aus v Elementen.
Die Summe der v Vektorelemente xi soll s ergeben.

Wir wissen anhand des Beispiels oben: Wenn wir v-1 Kugeln ziehen, dann können wir wie oben beschrieben aus jeder Ziehung v Vektorelemente erzeugen.
Insgesamt sollten nach dem Ziehen der v-1 Kugeln noch s Kugeln im Topf liegen.

Wir müssen also den Fall "Aus n=v-1+s Kugeln ohne Zurücklegen d=v-1 Kugeln ziehen" berechnen.

Dies kannst du
- rekursiv lösen oder
- iterativ indem du alle möglichen Fälle durchnummerierst und aus jeder Nummer einen Vektor erzeugst.