Möglichkeiten beim Verteilen von Kugeln?
Hallo, ich soll für den Matheunterricht ausrechnen, wie viele Möglichkeiten es gibt, wenn man 10 Kugeln in 3 Gefäße ,mit Platz für jeweils 10 Kugeln, einordnen möchte. Gibt es für so etwas eine Formel / ein Rechengesetz? Oder hilft da nur blindes ausprobieren? Danke im Voraus! :D
2 Antworten
Hier geht es um das allgemeine Problem, Kapazitäten zu füllen. Das Problem ist motiviert u. a. aus der Physik: N Kammern sind gegeben und jede wird mit einer diskreten Anzahl q[1], q[2], …, q[N] ≥ 0 von Teilchen gefüllt, wobei die Gesamtzahl der Teilchen ist q. Das heißt, von einer physikalischen Deutung völlig entkoppelt, geht es darum
F(N,q) := |{(q[1], q[2], …, q[N]) : q[1], q[2], …, q[N]≥0
∑q[k] = q}|
Dafür gibt es jawohl einen sehr einfachen Ausdruck:
F(N,q) = (q+N–1 über q).
Herleitung / Beweis zeig ich später. (Ach ja, dann in deinem Problem wäre die entsprechende Anzahl gleich F(3,10) = (3+10–1 über 3) = (12 über 3) = 220.)
Hier eine viel mehr kombinatorische Herleitung der Formel, an die ich gerade gedacht habe.
Man lege die q Teilchen aus hintereinander:
O O O O O O O O ··· O O
Es geht darum diese Folge in N Teile zu Scheiden. Dafür reichen aber N–1 Schnitte aus. Z. B. Für q=9 und N=5 wäre:
O O * O O O O O * * O * O
eine Anordnung von jeweils q[1]=2, q[2]=5, q[3]=0, q[4]=1, q[5]=1 Teilchen zu Plätzen 1, 2, 3, 4 bzw. 5.
Daraus ergibt sich, dass es darum geht q x O und N–1 x * untereinander zu sortieren. Dafür gibt exakt (N–1 + q)! / q!(N–1)! Möglichkeiten. Also F(N,q) = (N–1 + q)! / q!(N–1)! = (N–1 + q über N–1) usw.
Mir ist dann auch aufgefallen, dass 2. schon beachtet wird. Natürlich erst nachdem ich die Frage schon abgeschickt hatte. :P
Ich hab mir schon gedacht, dass die Formel, wenn 1 beachtet wird, kompliziert wird. Ist es zu kompliziert/schwer, dass du es hier erklären kannst?
Aber Danke dir, das hat mir schon weiter geholfen! ^^
Okay, schau mal, hier mein Ansatz (es gibt bestimmt andere).
Für eine Folge ƒ : ℤ ⟶ ℂ bezeichnen wir mit ƒ* : ℂ ⟶ ℂ die (partiell definierte) Funktion ƒ*(z) = ∑ ƒ(n)·zⁿ. Unter anderem lassen sich komplexe Konstruktionen auf der Folge-Ebene durch sehr einfache algebraische Operationen (Multiplikation, usw.) parallel durchgeführt werden. Z. B., falls ƒ, g Folge-Funktionen sind, so gilt für h : ℤ ⟶ ℂ gegeben durch h(n) = (f # g)(n) = ∑ f(n–k)g(k), dass h* = f*·g*. Wir haben folgende Korrespondenz (des lässt sich alles wasserdicht formalisieren, ich führe es nur kurz ein, um einen Überblick zu verschaffen)
FOLGE-EBENE TRANSFORMATION
----------------------------------
ƒ(n) ƒ*(z)
ƒ(n–k) zᵏƒ*(z)
ƒ#g ƒ*·g*
(n+k über k)ƒ(n+k) 1/k! (∂/∂z)ᵏƒ(z)
1 für n≥0 1/(1–z)
Tabelle 1.
Diese Eigenschaften kann man sehr leicht beweisen.
Nun betrachten wir das Problem. Man betrachte im Folgenden N als Parameter: es gilt F(N,q) Anzahl der Möglichkeit q Teilchen über N Plätze zu verteilen. Es gilt
F*(N,z) = ∑ F(N,q)·z^q
= ∑über q≥0 ∑∑…∑ᴺ z^q
über q[1]…q[N]≥0 mit ∑q[k]=q
= ∑über q≥0 ∑∑…∑ᴺ z^∑q[k]
über q[1]…q[N]≥0 mit ∑q[k]=q
= ∑∑…∑ᴺ ∏z^q[k]
über q[1]…q[N]≥0
= ∏ᴺ∑z^q[k]
über q[k]≥0
= 1/(1-z)ᴺ
= 1/(N–1)! (∂/∂z)ᴺ˜¹ 1/(1-z)
Tabelle 1 zufolge gilt F(N,q) = (N–1+q über N–1)·g(n), wobei g die Folge-Funktion ist mit Transformation g*(z) = 1/(1–z). Dies die nichts anderes als (laut Tabelle 1) die Funktion die überall 1 ist für Zahlen ≥0. Daher F(N,q) = (N–1+q über N–1) = (N–1 + q über q).
Doch was ist, wenn bedingt wird, dass jedes 0≤q[k]<Q für ein fixiertes Q? Dann ist die Herleitung exakt wie oben, nur mit dieser weiteren Bedingung in der N-fachen Summe eingebaut. Dies hat zur Folge, dass
F*(N,Q,z) = ∏ᴺ∑z^q[k]
über q[k] mit 0≤q[k]<Q
= ∏ᴺ (1–z^Q)/(1-z)
= (1–z^Q)ᴺ/(1-z)ᴺ
= ∑(N über k)(-1)ᵏz^kQ/(1-z)ᴺ
Laut Tabelle 1, ist F(N,Q,q) damit eine Summe (von k=0 bis Q) aus gewichteten Verschiebungen von F(N,Q). Es gilt
F(N,Q,q) = ∑(N über k) (-1)ᵏ F(N,q–kQ)
= ∑(N über k)(N–1+q–kQ über N–1)(-1)ᵏ
wobei F(N,·)=0 für negative Werte. Die Summen oben sind endlich und laufen von k=0 bis Q. Dieser Ausdruck ist … okay eigentlich nicht kompliziert. Doch schon aufwändig. Ob es eine Vereinfachung gibt?
Haha :D
Okay ,das muss ich erst einmal verkraften. Es kann eine Weile dauern bis ich das verstanden habe, aber ich bleibe dran :D. Vielen Dank für die Hilfe!
Und was passiert, wenn
1. Die Größe der Gefäße unterschiedlich ist
2. Es egal ist welche Kugel in welches Gefäß kommt, sondern nur die Anzahl der Kugeln im Gefäß relevant sind?
Danke dir schon mal! :D
Du kannst dir einen "Baum" zeichnen.
1
2
3
4
5
6
7
8
9
10
und hinter jede zahl wieder alle zahlen bis auf die die schon dort steht. und das so lange, bis alle zahlen in einem pfad vorgekommen sind. Das werden sehr viele Pfade. Die genaue Zahl ist hier 10^10 (10 hoch 10) also 10000000000. (Keine Garantie, ist schon länger her, dass ich das in der Schule gemacht habe.)
2. wurde ja vorausgesetzt in der Definition der Formel: ausgeblendet wird, welche Kugel wohin kommt, berücksichtigt wird nur, welches Gefäß (k) wieviel (q[k]) bekommt.
1. das wird nicht berücksichtigt. In der Formel wird vorausgesetzt, dass alle Gefäße (k) beliebig viele Kugeln (q[k]>=0… oder mindestens: 0<=q[k]<=q) enthalten kann.
Probleme mit beschränkten Kapazitäten sind deutlich komplizierter: da lässt sich was sagen über das asymptotische Verhalten, die Formel für endliche Werte ist jedoch recht kompliziert.