Kombinatorik: Anzahl Möglichkeiten k ununterscheidbare Elemente auf n Plätze zu verteilen mit Bedingung!

Question

Anzahl Möglichkeiten k ununterscheidbare Elemente auf n Plätze zu verteilen

Normal gilt hier die Formel

(n+k-1 über k)

Wenn ich die Bedingung habe das auf jedem Platz mind. p Elemente liegen sollen dann verteil ich diese vorher

k = k_alt - n*p

(n+k-1 über k)

Was aber wenn ich die Bedingung habe, das auf jedem Platz höchstens q Elemente liegen sollen.

Beispiel:

Wie viel Möglichkeiten habe ich 20 Euro an 4 Kinder zu verteilen, wenn jedes Kind mindestens 1 Euro und höchstens 9 Euro bekommen soll.

Oder allgemein

Wie viel Möglichkeiten habe ich k Euro an n Kinder zu verteilen, wenn jedes Kind mindestens p Euro und höchstens q Euro bekommen soll.

Answer 1

zuerst kann man das Problem:

"Wieviele Möglichkeiten habe ich, k Euro an n Kinder zu verteilen, wenn jedes Kind mindestens p Euro und höchstens q Euro bekommen soll."

zurückführen auf

"Wieviele Möglichkeiten habe ich, k* := k - np Euro an n Kinder zu verteilen, wenn jedes Kind mindestens 0 Euro und höchstens q* := q - p Euro bekommen soll."

Zum Trost vereinbaren wir jetzt, dass jedes Kind, das einen Euro nicht bekommen hat, einen Anti-Euro kriegt. Jedes Kind kann maximal k* Euros (oder k* Anti-Euros) kriegen. Die Anzahl der Anti-Euros beträgt k** = nk* - k* = (n - 1)k*. Das heißt die Aufgabe lässt sich zurückführen auf:

"Wieviele Möglichkeiten habe ich, k** Anti-Euros an n Kinder zu verteilen, wenn jedes Kind mindestens p** = k* - q* Anti-Euros kriegen soll."

Schließlich kann man diese Formulierung zurückführen auf:

"Wieviele Möglichkeiten habe ich, k*** = k** - np** Anti-Euro an n Kinder zu verteilen."

Dies führt zu (n über k***) = (n über (k** - np**)) = (n über ((n-1)k* - n(k* - q*))) = (n über (n-1)(k-np) - n(k-np - (q-p))) = ... = (n über nq - k).

MfG

Mister

Comments

Klingt soweit plausibel. Werde mich in der Woche mal dransetzen ob ich das so auf mein Problem was ich hatte anwenden kann.