Kombinatorik < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 13:42 Di 12.10.2010 | | Autor: | Hejo |
| Aufgabe | | Es seien [mm] n,k\in \IN^{\ast}. [/mm] Es sollen n ununterscheidbare Kugeln auf k Schachteln´verteilt werden. Jede Schachtel darf beliebig viele Kugeln enthalten. Es bezeichne [mm] z_{n,k} [/mm] die anzahl der verschiedenen Verteilungsmöglichkeiten. Man beweise, dass [mm] z_{n,k} [/mm] = [mm] \vektor{n+k-1 \\ n} [/mm] gilt. Hinweis: vollständige Induktion über k [mm] \in \IN^{\ast} [/mm] |
Meine Idee ist das ich den Ausdruck [mm] z_{n,k} [/mm] = [mm] \vektor{n+k-1 \\ n} [/mm] irgendwie in einen Ausdruck dieser Art [mm] \summe_{m=1}^{k}\vektor{n+m \\ m} [/mm] bringe und dann die vollständige Induktion durchführe.
Wäre das so richtig?
Aber wie komme ich auf einen Ausdruck [mm] \summe_{m=1}^{k}\vektor{n+m \\ m}?
[/mm]
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 13:49 Di 12.10.2010 | | Autor: | leduart |
Hallo
warum willst du das denn in ne Summe verwandeln? hast du bisher nur vollst Induktion mit Summen gemacht? du musst direkt an den Ausdruck rangehen und benutzen , was [mm]\vektor{m \\
n}[/mm] bedeutet. fang erstmal mit k=1 als Ind. anfang an. formulier dann die indvors und den induktionsschritt.
Gruss leduart
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:31 Di 12.10.2010 | | Autor: | Hejo |
OK
Induktionsanfang:
[mm] z_{n,1}=\vektor{n \\ n}=1
[/mm]
Dass heißt ich kann n Kugeln nur in eine schachtel packen und das ist offensichtlich wahr.
Ich setze vorraus das [mm] z_{n,k}=\vektor{n+k-1 \\ n}= [/mm] für alle k bereits wahr ist.
Es ist [mm] z_{n,k+1}=\vektor{n+k \\ n}=\vektor{n+k-1 \\ n}+\vektor{n+k \\ n} [/mm]
Aber ich glaube dass stimmt nicht:(
|
|
|
| |
|
Hallo Hejo,
> OK
> Induktionsanfang:
>
> [mm]z_{n,1}=\vektor{n \\
n}=1[/mm]
>
> Dass heißt ich kann n Kugeln nur in eine schachtel packen
> und das ist offensichtlich wahr.
Richtig.
> Ich setze vorraus das [mm]z_{n,k}=\vektor{n+k-1 \\
n}=[/mm] für
> alle k bereits wahr ist.
Nicht ganz. Du setzt voraus, dass es für ein bestimmtes k wahr ist, und zeigst dann, dass es dann auch für k+1 wahr ist. So geht Induktion.
> Es ist [mm]z_{n,k+1}=\vektor{n+k \\
n}=\vektor{n+k-1 \\
n}+\vektor{n+k \\
n}[/mm]
>
> Aber ich glaube dass stimmt nicht:(
Nee, das kann ja auch nicht stimmen. Dann müsste ja [mm] \vektor{n+k-1\\n}=0 [/mm] sein.
Wie geht denn der Induktionsschritt? Du nimmst an, Dein Formel gilt für ein bestimmtes k. Nun stellst Du eine Schachtel dazu, ohne die Zahl der Kugeln zu verändern. Die Frage ist doch, um wieviele Möglichkeiten sich die Zahl der möglichen Verteilungen damit ändert.
Hast Du dazu eine Idee?
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:52 Di 12.10.2010 | | Autor: | Hejo |
es müssten [mm] \vektor{n+1 \\ n} [/mm] mehr möglichkeiten geben oder?
aber wenn ich versuche dass auszurechnen komm ich auf [mm] \bruch{(n+k-1)!*k+(n+1)!*k!}{n!*k!}
[/mm]
und hier häng ich
|
|
|
| |
|
Hallo nochmal,
> es müssten [mm]\vektor{n+1 \\
n}[/mm] mehr möglichkeiten geben
> oder?
[NB: das wären also n+1 mehr Möglichkeiten]
Und woher hast Du diese Angabe? Kannst Du sie begründen? Ich hätte ja auf [mm] (k-1)!*e^{k\pi\delta} [/mm] getippt, mit [mm] \delta\in\IR\setminus\IQ. [/mm] Außerdem bin ich sicher, dass [mm] \delta=\delta_k(n) [/mm] ist. 
Mal ernsthaft. Du musst Deine Angabe schon begründen können, und zwar nicht aus der Induktionsannahme. Ansonsten hilft der Induktionsschritt ja nicht weiter.
Dazu kann man z.B. folgendes überlegen:
Fall 1) Die neue Schachtel ist leer. Dafür gibt es [mm] \vektor{n+k-1\\n} [/mm] Möglichkeiten (die "restlichen" n auf die ersten k Kästchen zu verteilen; das ist die Induktionsvoraussetzung).
Fall 2) Die neue Schachtel enthält 1 Kugel. Den Rest zu verteilen, geht auf [mm] \vektor{n-1+k-1\\n-1} [/mm] Weisen.
[...]
Fall n+1) Die neue Schachtel enthält alle n Kugeln. Dann gibt es nur eine Möglichkeit für die anderen Schachteln. Die sind nämlich alle leer. Diese eine Möglichkeit müsste sich auch [mm] \vektor{n-n+k-1\\n-n} [/mm] schreiben lassen. Jo, stimmt.
Fragt sich nun, ob es eine geschicktere Herangehensweise gibt, oder ob sich die n+1 Fälle zu einer hübscheren Summe zusammenfassen lassen.
Übrigens gibt es doch die schöne Addition [mm] \vektor{s\\t}+\vektor{s\\t+1}=\vektor{s+1\\t+1}.
[/mm]
Die müsste hier doch weiterhelfen.
> aber wenn ich versuche dass auszurechnen komm ich auf
> [mm]\bruch{(n+k-1)!*k+(n+1)!*k!}{n!*k!}[/mm]
>
> und hier häng ich
Nee, Du hängst schon vorher.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:52 Di 12.10.2010 | | Autor: | Hejo |
>
> Dazu kann man z.B. folgendes überlegen:
>
> Fall 1) Die neue Schachtel ist leer. Dafür gibt es
> [mm]\vektor{n+k-1\\n}[/mm] Möglichkeiten (die "restlichen" n auf
> die ersten k Kästchen zu verteilen; das ist die
> Induktionsvoraussetzung).
Die versteh ich irgendwie nich. könntest du das mal an einem Beispiel erläutern bitte?
Gruß und danke für die hilfe:)
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:28 Di 12.10.2010 | | Autor: | Hejo |
also ich würde sagen
[mm] \vektor{n+k\\n} [/mm] = [mm] \vektor{n+k-1\\n}+\summe_{m=0}^{n}\vektor{n-m+k-1\\n-m}
[/mm]
is dass so richtig ? wenn ja wie geht es dass weiter? ich weiß nich wie ich den vektor und die summe addieren kann...
|
|
|
| |
|
Hallo,
fast richtig. Entweder Du lässt m erst ab 1 laufen, dann stimmts. Oder Du lässt den Bin.koeff. vor der Summe weg, dann stimmts auch.
Tja, wie man diese Summe bildet, das ist wahrscheinlich das ganze Geheimnis der Aufgabe. Probiers mal. So viele Rechenregeln für Bin.koeff. gibts ja nicht. Notfalls halt alle auflösen in die Fakultätendarstellung und dann lustig drauflosrechnen.
Wenn Du Deine Gleichung (mit einer der beiden o.g. Änderungen) nachweisen kannst, ist der Induktionsschritt vollzogen.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:46 Mi 13.10.2010 | | Autor: | Hejo |
[mm] \vektor{n+k\\n}=\vektor{n+k-1\\n}+\summe_{m=1}^{n}\vektor{n-m+k-1\\n-m}
[/mm]
und
[mm] \vektor{n\\k}=\vektor{n-1\\k-1}+\vektor{n-1\\k}
[/mm]
Wenn ich in dieser Formel das n durch n+k und das k durch n ersetze erhalte ich:
[mm] \vektor{n+k\\k}=\vektor{n+k-1\\n-1}+\vektor{n+k-1\\n}
[/mm]
Also ich denk mal eigentlich müsste ich doch die Summe [mm] \summe_{m=1}^{n}\vektor{n-m+k-1\\n-m} [/mm] irgendwie ausrechen und dann auf [mm] \vektor{n+k-1\\n-1} [/mm] kommen, richtig?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:28 Do 14.10.2010 | | Autor: | Hejo |
Kann mir das jemand bestätigen?
grüße
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:12 Do 14.10.2010 | | Autor: | leduart |
Hallo
ja, kann ich
Gruss leduart
|
|
|
| |
|
Hallo Hejo,
da gibt es einen "Trick", der nötig ist, um diese Summe zu bestimmen.
Zu zeigen ist ja [mm] \vektor{n+k\\n}=\summe_{m=0}^{n}\vektor{n-m+k-1\\n-m}
[/mm]
Betrachten wir mal nur die letzten beiden Glieder der Summe.
Da steht [mm] \vektor{k\\1}+\vektor{k-1\\0}.
[/mm]
Nun macht man sich zunütze, dass ja für alle [mm] i\in\IN [/mm] gilt [mm] \vektor{i\\0}=1.
[/mm]
Damit ist die Summe der letzten beiden Glieder umzuformulieren:
[mm] \vektor{k\\1}+\vektor{\blue{k-1}\\0}=\vektor{k\\1}+\vektor{\blue{k}\\0}=\vektor{k+1\\1}
[/mm]
Und ab da kann man prima weiterrechnen, bis sich die zu zeigende Gleichheit ergibt.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:44 Fr 15.10.2010 | | Autor: | Hejo |
Ok ich versuchs mal;)
Ich fasse noch mal zusammen:
Ich habe eine Formel [mm] \vektor{n+k-1\\n} [/mm] und soll zeigen dass diese gilt.
jetzt hab ich mir über legt, dass wenn ich eine Schachtel hinzufüge, gibtes wenn die schachtel leer ist genau die Möglichkeiten, die ich bei k-1 Schachteln habe. Dann kommen die Möglichkeiten hinzu wenn ich eine Kugel in die neue schachtel stecke. Dann sind es die Möglichkeiten die ich erhalte wenn ich n-1 Kugelen auf k -1 schachteln verteile usw. daraus erhalte ich folgende Gleichung: [mm] \summe_{m=0}^{n}\vektor{n-m+k-1\\n-1}
[/mm]
Zu zeigen ist:
[mm] \vektor{n+k\\n}=\vektor{n+k-1\\n}+\summe_{m=1}^{n}\vektor{n-m+k-1\\n-m}=\summe_{m=0}^{n}\vektor{n-m+k-1\\n-m}
[/mm]
[mm] \vektor{n+k\\n}=\summe_{m=0}^{n-2}\vektor{n-m+k-1\\n-m}+\vektor{k+1\\1}
[/mm]
nee tut mir leid ich komm nich weiter^^
grüße
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:30 Fr 15.10.2010 | | Autor: | Hejo |
kann sich das mal jemand anschauen bitte:)
gruß
|
|
|
| |
|
Hallo Hejo,
wo ist denn jetzt das Problem? Hast Du den Trick an der Rechnung verstanden? Geht es nur noch darum, wie Du es aufschreibst?
Die Erläuterung, wie der Induktionsschluss zustandekommt, mithin die zu zeigende Rechnung, sieht mir noch schwer nachvollziehbar aus.
Und wenn es nur noch um die Darstellung der Rechnung geht, hätte ich schon noch eine Idee...
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:16 Fr 15.10.2010 | | Autor: | Hejo |
Hey,
ich hab nich wirklich verstanden warum du die beiden letzten terme rausnimmst. Und was fang mit der Summe an, wenn ich die bis n-2 laufen lasse? ich denk mal, wenn ich das mit dem "trick" verstanden habe und das noch hinschreibe dürfte es mit der Darstellung passen!?
gruß hejo
|
|
|
| |
|
Hallo nochmal,
du hast es also nicht selbst nachgerechnet, oder?
Wenn Du die letzten beiden Terme zusammenfasst, kommt einer heraus, den man mit dem drittletzten Term wieder wunderbar zusammenfassen kann zu einem, der dann mit dem viertletzten...
Es ist nämlich
[mm] \summe_{m=0}^{n}\vektor{n-m+k-1\\n-m}=\left(\summe_{m=0}^{n-2}\vektor{n-m+k-1\\n-m}\right)+\vektor{k\\1}+\vektor{k-1\\0}=\left(\summe_{m=0}^{n-2}\vektor{n-m+k-1\\n-m}\right)+\vektor{k\\1}+\vektor{k\\0}=
[/mm]
[mm] =\left(\summe_{m=0}^{n-2}\vektor{n-m+k-1\\n-m}\right)+\vektor{k+1\\1}=
[/mm]
Bis hierher ist das ja schon bekannt. Die letzten zwei Glieder... weiter:
[mm] =\left(\summe_{m=0}^{n-3}\vektor{n-m+k-1\\n-m}\right)+\vektor{k+1\\2}+\vektor{k+1\\1}=\left(\summe_{m=0}^{n-3}\vektor{n-m+k-1\\n-m}\right)+\vektor{k+2\\2}=\ \cdots
[/mm]
[mm] \cdots\ =\left(\summe_{m=0}^{n-a}\vektor{n-m+k-1\\n-m}\right)+\vektor{k+a-1\\a-1}=\ \cdots\ =\vektor{n+k-1\\n}+\vektor{n+k-1\\n-1}=\vektor{n+k-1\\n}
[/mm]
wzzw.
(puuh, erst im dritten Anlauf. Der neue Editor schafft mich...)
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:07 Fr 15.10.2010 | | Autor: | Hejo |
Ahhh;)
Vielen Dank für die Mühe!
grüße
Hejo
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:10 Fr 15.10.2010 | | Autor: | reverend |
Gern geschehen. 
|
|
|
|
