Bestimmung der Mächtigkeit < Sonstiges < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:38 Fr 11.04.2014 | | Autor: | X3nion |
| Aufgabe | | Sei n [mm] \in \IN. [/mm] Man bestimme die Anzahl aller Tripel [mm] (k_{1}, k_{2}, k_{3}) \in \IN^{3} [/mm] mit [mm] k_{1} [/mm] + [mm] k_{2} [/mm] + [mm] k_{3} [/mm] = n. |
Einen wunderschönen guten Abend zusammen!
Ich habe eine Frage zu folgender Aufgabe. Im Endeffekt bestimme ich ja nichts anderes als die Mächtigkeit der Menge M bestehend aus den Tripeln [mm] (k_{1}, k_{2}, k_{3}) [/mm] , sodass [mm] k_{1} [/mm] + [mm] k_{2} [/mm] + [mm] k_{3} [/mm] = n.
Ist n=0: [mm] M_{0} [/mm] = [mm] \{ (0,0,0) \} [/mm] => [mm] |M_{0}| [/mm] = 1
Ist n=1: [mm] M_{1} [/mm] = [mm] \{ (1,0,0) , (0,1,0), (0,0,1) \} [/mm] => [mm] |M_{1}| [/mm] = 3
Ist n=2: [mm] M_{2} [/mm] = [mm] \{ (1,1,0), (1,0,1), (0,1,1), (2,0,0), (0,2,0), (0,0,2) \} [/mm] => [mm] |M_{2}| [/mm] = 6
Ist n=3: [mm] M_{3}= \{ (3,0,0) , (0,3,0), (0,0,3), (2,1,0), (2,0,1), (1,2,0), (1,0,2), (0,1,2), (0,2,1), (1,1,1) \} [/mm] => [mm] |M_{3}| [/mm] = 10
Ist n=4: [mm] |M_{4}| [/mm] = 15
... Insgesamt komme ich auf die Vermutung, dass sich die Differenz zwischen den Mächtigkeiten immer um 1 erhöht, also:
[mm] |M_{1}| [/mm] - [mm] |M_{0}| [/mm] = 2
[mm] |M_{2}| [/mm] - [mm] |M_{1}| [/mm] = 3
[mm] |M_{3}| [/mm] - [mm] |M_{2}| [/mm] = 4
[mm] |M_{4}| [/mm] - [mm] |M_{3}| [/mm] = 5
Und insgesamt komme ich somit auf folgende Formel zur Berechnung der Mächtigkeit: [mm] \summe_{k=0}^{n} [/mm] (k+1) bzw. explizit bestimmt: [mm] \frac{(n+1)(n+2)}{2}
[/mm]
Die Frage aller Fragen ist nun jedoch: Wie beweise ich, dass die Summenformel bzw. die explizite Formel gilt? Ich habe ja nur den Verdacht dass sich die Differenz der Mächtigkeiten jeweils um 1 erhöht!
Viele Grüße und auf Antwort hoffend,
Christian! 
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 19:55 Fr 11.04.2014 | | Autor: | hippias |
Man koennte versuchen einen Zusammenhang zwischen den Tripeln aus [mm] $M_{n}$ [/mm] und [mm] $M_{n+1}$ [/mm] herzustellen, der eine Funktion [mm] $f:M_{n}\to M_{n+1}$ [/mm] liefert. Wenn sie Injektiv ist, wuesste man schon einmal, dass [mm] $|M_{n+1}|= |M_{n}|+x_{n}$ [/mm] ist, wobei [mm] $x_{n}:= |M_{n+1}\backslash f(M_{n})|$ [/mm] ist (der Rest). Wenn man diesen Rest noch auszaehlen kann, dann waere man fertig.
Mein Tip: Zerlege [mm] $M_{n+1}$ [/mm] in die Tupel, deren erster Eintrag $=0$ ist und die, deren erster Eintrag $>0$ ist. Die ersteren Tupel sollten sich gut durchzaehlen lassen. Ueberlege Dir dann, dass die Menge der anderen Tupel gleichmaechtig zu [mm] $M_{n}$ [/mm] ist.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:18 Fr 11.04.2014 | | Autor: | abakus |
> Sei n [mm]\in \IN.[/mm] Man bestimme die Anzahl aller Tripel [mm](k_{1}, k_{2}, k_{3}) \in \IN^{3}[/mm]
> mit [mm]k_{1}[/mm] + [mm]k_{2}[/mm] + [mm]k_{3}[/mm] = n.
> Einen wunderschönen guten Abend zusammen!
>
> Ich habe eine Frage zu folgender Aufgabe. Im Endeffekt
> bestimme ich ja nichts anderes als die Mächtigkeit der
> Menge M bestehend aus den Tripeln [mm](k_{1}, k_{2}, k_{3})[/mm] ,
> sodass [mm]k_{1}[/mm] + [mm]k_{2}[/mm] + [mm]k_{3}[/mm] = n.
>
> Ist n=0: [mm]M_{0}[/mm] = [mm]\{ (0,0,0) \}[/mm] => [mm]|M_{0}|[/mm] = 1
>
> Ist n=1: [mm]M_{1}[/mm] = [mm]\{ (1,0,0) , (0,1,0), (0,0,1) \}[/mm] =>
> [mm]|M_{1}|[/mm] = 3
>
> Ist n=2: [mm]M_{2}[/mm] = [mm]\{ (1,1,0), (1,0,1), (0,1,1), (2,0,0), (0,2,0), (0,0,2) \}[/mm]
> => [mm]|M_{2}|[/mm] = 6
>
> Ist n=3: [mm]M_{3}= \{ (3,0,0) , (0,3,0), (0,0,3), (2,1,0), (2,0,1), (1,2,0), (1,0,2), (0,1,2), (0,2,1), (1,1,1) \}[/mm]
> => [mm]|M_{3}|[/mm] = 10
>
> Ist n=4: [mm]|M_{4}|[/mm] = 15
>
> ... Insgesamt komme ich auf die Vermutung, dass sich die
> Differenz zwischen den Mächtigkeiten immer um 1 erhöht,
> also:
> [mm]|M_{1}|[/mm] - [mm]|M_{0}|[/mm] = 2
> [mm]|M_{2}|[/mm] - [mm]|M_{1}|[/mm] = 3
> [mm]|M_{3}|[/mm] - [mm]|M_{2}|[/mm] = 4
> [mm]|M_{4}|[/mm] - [mm]|M_{3}|[/mm] = 5
>
> Und insgesamt komme ich somit auf folgende Formel zur
> Berechnung der Mächtigkeit: [mm]\summe_{k=0}^{n}[/mm] (k+1) bzw.
> explizit bestimmt: [mm]\frac{(n+1)(n+2)}{2}[/mm]
>
> Die Frage aller Fragen ist nun jedoch: Wie beweise ich,
> dass die Summenformel bzw. die explizite Formel gilt? Ich
> habe ja nur den Verdacht dass sich die Differenz der
> Mächtigkeiten jeweils um 1 erhöht!
>
> Viele Grüße und auf Antwort hoffend,
> Christian!
Hallo,
du kommst sicher schnell zum Ziel, wenn du keine Fallunterscheidung über mögliche n machst, sondern für ein beliebiges festes n über die möglichen Werte von [mm] $k_1$.
[/mm]
Für [mm] $k_1=n$ [/mm] gibt es nur eine Möglichkeit (die beiden anderen Summanden sind 0).
Für [mm] $k_1=n-1$ [/mm] gibt es nur zwei Möglichkeit (die beiden anderen Summanden sind 0+1 oder 1+0).
Für [mm] $k_1=n-2$ [/mm] gibt es nur drei Möglichkeit (die beiden anderen Summanden sind 0+2 oder 1+1 oder 2+0).
...
Für [mm] $k_1=0 [/mm] $ gibt es (n+1) Möglichkeit (die beiden anderen Summanden sind 0+n, 1+(n-1), 2+(n-2),...,n+0).
Also gibt es insgesamt 1+2+3+...+(n+1) Möglichkeiten.
(Siehe "Gaußsche Summenformel"
und "Dreieckszahlen).
Gruß Abakus
|
|
|
| |
|
Die folgende Idee funktioniert mit beliebig vielen Summanden, deren Anzahl fest vorgegeben ist:
Bilde eine Kette aus n+k-1 Kästchen für die Zahl n und die k Summanden, hier also n+2.
Suche dir k-1 (also hier 2) von diesen Kästchen aus und schreibe ein Kreuz hinein. n Kästchen bleiben frei.
Die freien Kästchen links vom ersten Kreuz bilden den ersten Summanden, die zwischen dem ersten und zweiten Kreuz den zweiten, die zwischen dem zweiten und dritten den dritten Summanden usw. und die hinter dem letzten Kreuz den letzten Summanden. Folgen zwei Kreuze direkt aufeinander, so ist der Summand zwischen ihnen 0.
Du bekommst nun die Anzahl aller möglichen Summanden, indem du alle Möglichkeiten berechnest, wie du aus n+k-1 Kästchen k-1 für die Kreuze aussuchen kannst. Dafür gibt es genau [mm] \vektor{n+k-1 \\ k-1} [/mm] Möglichkeiten.
In deinem Beispiel mit k=3 sind das [mm] \vektor{n+2 \\ 2}= \bruch{(n+2)!}{n!*2!}=\bruch{(n+2)(n+1)}{2}
[/mm]
Beispiel: [mm] \Box\Box\Box\Box X\Box\Box X\Box\Box\Box [/mm] entspricht 4+2+3=9
[mm] \Box\Box\Box\Box X\Box\Box\Box\Box\Box [/mm] X entspricht 4+5+0=9
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:03 Do 17.04.2014 | | Autor: | X3nion |
Hallo Leute!
Vielen vielen Dank euch für eure Bemühungen, ich habe alles verstaneden und es ist mir voll und ganz ersichtlich!
|
|
|
|
