Auf n Zellen sollen k nicht unterscheidbare Teilchen verteilt werden

Neue Frage »

diosmio Auf diesen Beitrag antworten »
Auf n Zellen sollen k nicht unterscheidbare Teilchen verteilt werden
Meine Frage:
Hallo!

Es geht um folgende Aufgabe:

Auf n Zellen sollen k nicht unterscheidbare Teilchen so verteilt werden, dass jede Zelle höchstens ein Teilchen enthält.

Zeigen Sie: Es gibt genau verschiedene Verteilungen.


Meine Ideen:
Ich möchte diese Aufgabe mit der vollständigen Induktion zeigen.
Das Prinzip der vollständigen Induktion ist mir bekannt.
Nur habe ich hier dabei Probleme einen Anfang zu finden.


Laut Aufgabe soll ich also beweisen?


Kann ich also von ausgehen?
Und desweiteren müsste ich dann ja auch 2 vollständige Induktionen für n und k durchführen. Da ja beide variabel sind... (5 Zellen und 2 Teilchen oder 9 Zellen und 3 Teilchen)


Bei anderen Beispielen hat man ja oft eine Gleichung gegeben.
(Z.B.: Links eine Summe und Rechts irgend ein Term)

In diesem Fall hab ich ja jetzt eigentlich nur eine Seite der Gleichung.

Stimmt meine Überlegung soweit oder lieg ich falsch?
Hasgar Auf diesen Beitrag antworten »
RE: Auf n Zellen sollen k nicht unterscheidbare Teilchen verteilt werden
Zitat:
Original von diosmio
Meine Frage:
Und desweiteren müsste ich dann ja auch 2 vollständige Induktionen für n und k durchführen.


Wenn Du die Aufgabe mit vollständiger Induktion lösen willst, dann musst Du die Induktion über n oder k führen. Beides gleichzeitig geht nicht.

Zitat:
Original von diosmio
Meine Frage:
Kann ich also von ausgehen?


Wenn Ihr den Binomialkoeffizienten so definiert habt, dann musst Du sogar davon ausgehen. Wenn Ihr es anders definiert habt, dann nimm die entsprechende Definition.
sixty-four Auf diesen Beitrag antworten »
RE: Auf n Zellen sollen k nicht unterscheidbare Teilchen verteilt werden
Ich meine, du kannst dir das k zunächst als Konstante im Intervall



denken. Dann führst du den Beweis, indem du von n auf n+1 schliesst. Wenn du über k keine weiteren Annahmen machst, gilt das dann automatisch für alle natürlichen

diosmio Auf diesen Beitrag antworten »

Zitat:
Wenn Ihr den Binomialkoeffizienten so definiert habt, dann musst Du sogar davon ausgehen. Wenn Ihr es anders definiert habt, dann nimm die entsprechende Definition.


Mich verwirrt, dass ich zeigen soll.

Ich weiß also nicht, dass
die Anzahl der oben genannten Möglichkeiten sind.


D.h., um es zu prüfen muss ich wissen wie ich die Anzahl der Möglichkeiten berechnen kann.


Und das wäre eben

Stimmt das so?
sixty-four Auf diesen Beitrag antworten »

Zitat:
Original von diosmio

D.h., um es zu prüfen muss ich wissen wie ich die Anzahl der Möglichkeiten berechnen kann.



Für den Beweis spielt es eigentlich keine Rolle ob du weisst, wie man die Anzahl der Möglichkeiten berechnet. Du musst nur wissen, wie sich die Anzahl der Möglichkeiten verändert, wenn du von n Zellen zu n+1 Zellen übergehst.
sixty-four Auf diesen Beitrag antworten »

Zitat:
Original von sixty-four
Für den Beweis spielt es eigentlich keine Rolle ob du weisst, wie man die Anzahl der Möglichkeiten berechnet. Du musst nur wissen, wie sich die Anzahl der Möglichkeiten verändert, wenn du von n Zellen zu n+1 Zellen übergehst.


Wenn du trotzdem wissen willst, wie man auf die Formel kommt, kommt hier eine mögliche Erklärung:

Stelle dir vor, dass du jeder Zelle, die ein Teilchen enthält eine 1 und jeder Zelle, die kein Teilchen enthält eine 0 zuordnest. Dann entspricht einer jeden möglichen Belegung eine Folge von Binärziffern mit genau k Einsen und n-k Nullen. Du musst jetzt also ermitteln, wie viele n-stellige Binärzahlen es gibt, die genau k Einsen (und demzufolge n-k Nullen) enthalten. Das ist aber eine Permutationsaufgabe, wo es 2 Gruppen nicht unterscheidbarer Elemente gibt. Die Anzahl der möglichen Permutationen von n Elementen ist aber n! Wenn du eine Vertauschung innerhalb einer Gruppe vornimmst (also entweder Nullen untereinander tauscht oder Einsen) ändert sich nichts. Deshalb musst du die erwähnte Anzahl von n! durch die Anzahl der Möglichkeiten dividieren, die du hast um innerhalb einer Gruppe zu tauschen. Da du k Einsen und n-k Nullen hast, sind das k! bzw (n-k)!
Damit hast du für die Anzahl

 
 
diosmio Auf diesen Beitrag antworten »

Zitat:
Wenn du trotzdem wissen willst, wie man auf die Formel kommt, kommt hier eine mögliche Erklärung: Stelle dir vor, dass du jeder Zelle, die ein Teilchen enthält eine 1 und jeder Zelle, die kein Teilchen enthält eine 0 zuordnest. Dann entspricht einer jeden möglichen Belegung eine Folge von Binärziffern mit genau k Einsen und n-k Nullen. Du musst jetzt also ermitteln, wie viele n-stellige Binärzahlen es gibt, die genau k Einsen (und demzufolge n-k Nullen) enthalten. Das ist aber eine Permutationsaufgabe, wo es 2 Gruppen nicht unterscheidbarer Elemente gibt. Die Anzahl der möglichen Permutationen von n Elementen ist aber n! Wenn du eine Vertauschung innerhalb einer Gruppe vornimmst (also entweder Nullen untereinander tauscht oder Einsen) ändert sich nichts. Deshalb musst du die erwähnte Anzahl von n! durch die Anzahl der Möglichkeiten dividieren, die du hast um innerhalb einer Gruppe zu tauschen. Da du k Einsen und n-k Nullen hast, sind das k! bzw (n-k)! Damit hast du für die Anzahl


Ja so ganz nachvollziehen kann ich das jetzt nicht auf die Schnelle. Muss ich mir später nochmal zu Gemüte führen.



Ja ich würde es nun so anschreiben:



Ind. Anfang: n=1

Um eine gültige Anzahl zu erzielen muss es mindestens eine Zelle und mindestens so viel Zellen wie Teilchen geben.

daher:


Wenn n=1 kann k nur 1 sein.

Das ergibt dann 1 für den Induktions Anfang. Ist also wahr.

Ind. Schritt: n=n+1










Wenn man k! wegkürzt sieht das ganze dann etwas verwirrend aus. Deshalb schreibe ich es mit dem Produkt an.







Der Bruch auf der rechten Seite entspricht immer dem Produkt auf der linken Seite.
Der Nenner enthält immer um k weniger Elemente als der Zähler.
Genau diese k Elemente bildet das Produkt der linken Seite.


Hoffe das stimmt so Gott

Müsste ich jetzt eigentlich noch eine Induktion für k durchführen?
Bis jetzt wäre es ja nur für das n bewiesen...
sixty-four Auf diesen Beitrag antworten »

Das ist viel zu viel Rechnerei für meinen Geschmack. Ausserdem kann ich überhaupt nicht erkennen, wo du die Induktionsvoraussetzung benutzt, um die Behauptung zu beweisen.
Ich schlage mal vor, für die Anzahl der Möglichkeiten k Teilchen auf n Zellen zu verteilen ein Symbol, etwa



einzuführen. Dann ist die Induktionsvoraussetzung:



jetzt sollst du beweisen, dass unter dieser Voraussetzung



gilt. Dazu musst du dir überlegen, was mit der Anzahl der Möglichkeiten passiert, wenn eine weitere (n+1)-te Zelle hinzukommt.
diosmio Auf diesen Beitrag antworten »

Ich würde jetzt nur auf diese Möglichkeit kommen die Ind. Voraussetzung zu nützen:









Hierbei müsste ich dann ja wissen, dass die Anzahl sich mit folgendem Faktor verändert.

Zitat:
Für den Beweis spielt es eigentlich keine Rolle ob du weisst, wie man die Anzahl der Möglichkeiten berechnet. Du musst nur wissen, wie sich die Anzahl der Möglichkeiten verändert, wenn du von n Zellen zu n+1 Zellen übergehst.


Meintest du das damit?
sixty-four Auf diesen Beitrag antworten »

Zitat:
Original von diosmio

Hierbei müsste ich dann ja wissen, dass die Anzahl sich mit folgendem Faktor verändert.


Ja das ist richtig. Du musst dir jetzt überlegen, wie es zu diesem Faktor kommt. Dann gibt es auch nicht mehr viel zu rechnen.

Zitat:
Original von diosmio
Zitat:
Für den Beweis spielt es eigentlich keine Rolle ob du weisst, wie man die Anzahl der Möglichkeiten berechnet. Du musst nur wissen, wie sich die Anzahl der Möglichkeiten verändert, wenn du von n Zellen zu n+1 Zellen übergehst.


Meintest du das damit?


Ganz genau.
diosmio Auf diesen Beitrag antworten »

Ja aber dann komme ich ja nicht drumrum die ganze Formel herzuleiten oder?

Das hab ich jetzt mal gemacht:

Angenommen ich habe 8 Zellen und 3 Teilchen.
Nun fange ich an die Teile auf die Zellen zu verteilen.
Für das 1. Teilchen habe ich 8 mal die Möglichkeit, für das 2. dann 7 mal die Möglichkeit und für das 3. nur mehr 6 mal.

Die Anzahl der Möglichkeiten ergeben sich nun aus der Multiplikation:

d.h. 8*7*6 = Anzahl der Möglichkeiten die Teilchen in einer bestimmten Reihenfolge zu verteilen.

Um diesen Vorgang allgemein auszudrücken komtm nun die Fakultät ins Spiel.



Verallgemeinert gilt dann:

Die Anzahl der Möglichkeiten unter Berücksichtigung der Reihenfolge


Der Grund warum man durch k! noch dividieren muss ist dann schon etwas schwieriger zu erklären:


Zuerst stellt man sich die Frage auf wieviele Unterschiedliche Arten ich die 3 Teilchen untereinander anordnen kann.
Das Funktioniert wieder nach dem selben Prinzip wie oben:

Für das 1. Teilchen habe ich 3 Möglichkeiten, für das 2. dann 2 und für das letzte dann nur mehr 1.

3*2*1 = k!

Angenommen ich weiß wie oft die Teilchen veteilt werden können. Nun gehe ich her und nummeriere die Teilchen und will wissen wie oft ich sie unter Berücksichtigung aller möglichen Reihenfolgen einsortieren kann. (123, 132,312,....)

Daraus folgt, dass ich sie für jede mögliche Anordnung ohne Reihenfolge, k! mal unterschiedlich anordnen kann.






Oben hatte ich ja festgelegt:


Und das ergibt dann endlich:



Setze ich oben dann für n n+1 ein,



Damit weiß ich nun das der Faktor stimmt.


Falls mein Beweis nun so als richtig durchgeht, so ist es für mich immer noch etwas verwirrend.
Durch meine Herleitung jetzt habe ich es ja eigentlich schon längst bewiesen, oder nicht??

Das ist ja so definiert:



Edit: Rechschreibfehler Augenzwinkern
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »