Suche Bildungsgesetz für Folge < Sonstiges < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 08:56 Mi 17.06.2009 | | Autor: | Pille456 |
| Aufgabe | [mm] M_1=\{0,1\} [/mm]
[mm] M_2=\{2,4,6,8,10...\} [/mm]
[mm] M_3=\{0,1,2,3\}
[/mm]
Sei [mm] c_k [/mm] die Anzahl der Möglichkeiten k [mm] \in \IN [/mm] als Summe von [mm] a_1,a_2,a_3, [/mm] wobei [mm] a_k \in M_k [/mm] mit k = 1,2,3 darzustellen. Berechnen Sie die erzeugende Funktion [mm] \summe_{ik=0}^{\infty}c_k*t^k [/mm] |
Hi!
Also die erzeugende Funktion aufzustellen, wenn ich für [mm] c_k [/mm] ein Bildungsgesetz habe (sei es rekursiv oder sonst wie) kann ich hinbekommen denke ich, nur wie komme ich auf dieses Bildungsgesetz?
Ich habe mir mal für k = 0...6 die verschiedenen Möglichkeiten aufgeschrieben und kam dabei auf folgende Anzahlen:
k = 1 [mm] \Rightarrow c_k [/mm] = 0
k = 2 [mm] \Rightarrow c_k [/mm] = 1
k = 3 [mm] \Rightarrow c_k [/mm] = 2
k = 4 [mm] \Rightarrow c_k [/mm] = 3
k = 5 [mm] \Rightarrow c_k [/mm] = 4
k = 6 [mm] \Rightarrow c_k [/mm] = 4
Also gilt offensichtlich folgendes: [mm] c_k [/mm] = [mm] =\begin{cases} n-1, & \mbox{für } 1\le k \le 5 \\ 4, & \mbox{für } k \ge 5 \end{cases}
[/mm]
Soll ich nun zwei verschiedene erzeugende Funktionen bauen oder wie geht man da vor? Oder habe ich die Aufgabe falsch interpretiert?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 09:33 Mi 17.06.2009 | | Autor: | statler |
Hallo!
> [mm]M_1=\{0,1\}[/mm]
> [mm]M_2=\{2,4,6,8,10...\}[/mm]
> [mm]M_3=\{0,1,2,3\}[/mm]
> Sei [mm]c_k[/mm] die Anzahl der Möglichkeiten k [mm]\in \IN[/mm] als Summe
> von [mm]a_1,a_2,a_3,[/mm] wobei [mm]a_k \in M_k[/mm] mit k = 1,2,3
> darzustellen. Berechnen Sie die erzeugende Funktion
> [mm]\summe_{ik=0}^{\infty}c_k*t^k[/mm]
> Hi!
> Also die erzeugende Funktion aufzustellen, wenn ich für
> [mm]c_k[/mm] ein Bildungsgesetz habe (sei es rekursiv oder sonst
> wie) kann ich hinbekommen denke ich, nur wie komme ich auf
> dieses Bildungsgesetz?
> Ich habe mir mal für k = 0...6 die verschiedenen
> Möglichkeiten aufgeschrieben und kam dabei auf folgende
> Anzahlen:
> k = 1 [mm]\Rightarrow c_k[/mm] = 0
> k = 2 [mm]\Rightarrow c_k[/mm] = 1
> k = 3 [mm]\Rightarrow c_k[/mm] = 2
> k = 4 [mm]\Rightarrow c_k[/mm] = 3
> k = 5 [mm]\Rightarrow c_k[/mm] = 4
> k = 6 [mm]\Rightarrow c_k[/mm] = 4
>
> Also gilt offensichtlich folgendes: [mm]c_k[/mm] = [mm]=\begin{cases} n-1, & \mbox{für } 1\le k \le 5 \\ 4, & \mbox{für } k \ge 5 \end{cases}[/mm]
>
Also gilt offensichtlich folgendes: [mm]c_k[/mm] = [mm]=\begin{cases} k-1, & \mbox{für } 1\le k \le 5 \\ 4, & \mbox{für } k \ge 5 \end{cases}[/mm]
Damit bist du doch fertig, wobei ich das Wort 'offensichtlich' noch durch einen Beweis untermauern würde.
Wenn du alle [mm] c_k [/mm] kennst, kennst du die erzeugende Funktion. Man könnte die erzeugende Funktion auch einfach hinschreiben:
[mm] \summe_{k=0}^{\infty}c_k*t^k [/mm] = (1 + [mm] x)(x^2 [/mm] + [mm] x^4 [/mm] + [mm] x^6 [/mm] + [mm] \ldots)(1 [/mm] + x + [mm] x^2 [/mm] + [mm] x^3)
[/mm]
Auf der rechten Seite kann man jetzt noch reichlich umformen.
Gruß aus HH-Harburg
Dieter
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:09 Mi 17.06.2009 | | Autor: | Pille456 |
Also erstmal der Beweis, dass es gilt:
für 1 [mm] \le [/mm] k [mm] \le [/mm] 5: klar, einfach durchprobieren.
für k [mm] \ge [/mm] 5:
Wenn k gerade ist, gelten folgende Kombinationen: (0,k,0), (0,k-2,2), (1,k-2,1),(1,k-4,3)
Wenn k ungerade ist, gelten folgende Kombinationen: (0,k-1,1), (1,k-1,0) (0,k-3,3),(1,k-3,2)
Wobei z.B. (0,k,0) ein Tripel [mm] (a_1,a_2,a_3) [/mm] ist.
Damit wäre ich dann quasi schon fertig oder wie?
Zum zweiten Ansatz:
$ [mm] \summe_{k=0}^{\infty}c_k\cdot{}x^k [/mm] $ = (1 + [mm] x)(x^2 [/mm] $ + $ [mm] x^4 [/mm] $ + $ [mm] x^6 [/mm] $ + $ [mm] \ldots)(1 [/mm] $ + x + $ [mm] x^2 [/mm] $ + $ [mm] x^3) [/mm] = [mm] (1+2x+2x^2+2x^3+x^4)(x^2+x^4+x^6+...)
[/mm]
Weiter ausmultiplizieren wäre hier irgendwie relativ aufwendig....
Aber eine Frage hab ich dazu dann doch noch:
Also du hast ja nun immer [mm] "x^{Ein Element der Menge}" [/mm] aufgeschrieben und multiplizierst dies miteinander. Das hat sicherlich einen kombinatorischen Hintergrund, dass das so geht. Nur welchen genau?
Es erinnert etwas an den Multinominalkoeffiziernt, wenn man für eine Gleichung [mm] (x+y+z)^n [/mm] z.B. den Koeffizienten für [mm] x^2y^3z^5 [/mm] herausfinden möchte, aber so wirklich damit in Verbindung bekomme ich das nicht oder welche "Magie" ist dahinter?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 11:48 Mi 17.06.2009 | | Autor: | statler |
Mahlzeit!
> Also erstmal der Beweis, dass es gilt:
> für 1 [mm]\le[/mm] k [mm]\le[/mm] 5: klar, einfach durchprobieren.
> für k [mm]\ge[/mm] 5:
> Wenn k gerade ist, gelten folgende Kombinationen: (0,k,0),
> (0,k-2,2), (1,k-2,1),(1,k-4,3)
> Wenn k ungerade ist, gelten folgende Kombinationen:
> (0,k-1,1), (1,k-1,0) (0,k-3,3),(1,k-3,2)
> Wobei z.B. (0,k,0) ein Tripel [mm](a_1,a_2,a_3)[/mm] ist.
> Damit wäre ich dann quasi schon fertig oder wie?
Das ist ausführlich genug, würde ich sagen.
> Zum zweiten Ansatz:
> [mm]\summe_{k=0}^{\infty}c_k\cdot{}x^k[/mm] = (1 + [mm]x)(x^2[/mm] [mm]+[/mm] [mm]x^4[/mm] [mm]+[/mm]
> [mm]x^6[/mm] [mm]+[/mm] [mm]\ldots)(1[/mm] [mm]+ x +[/mm] [mm]x^2[/mm] [mm]+[/mm] [mm]x^3)[/mm] =
> [mm](1+2x+2x^2+2x^3+x^4)(x^2+x^4+x^6+...)[/mm]
> Weiter ausmultiplizieren wäre hier irgendwie relativ
Ausmultiplizieren war gar nicht gemeint. Der mittlere Term ist doch eine geometrische Reihe und folglich = [mm] \frac{x^2}{1 - x^2} [/mm] = [mm] \frac{x^2}{(1 - x)(1 + x)}
[/mm]
Der dritte Term ist gleich [mm] \frac{1 - x^4}{1 - x} [/mm] = [mm] \frac{(1 - x^2)(1 + x^2)}{1 - x} [/mm] = [mm] \frac{(1 - x)(1 + x)(1 + x^2)}{1 - x}
[/mm]
> aufwendig....
> Aber eine Frage hab ich dazu dann doch noch:
> Also du hast ja nun immer [mm]"x^{Ein Element der Menge}"[/mm]
> aufgeschrieben und multiplizierst dies miteinander. Das hat
> sicherlich einen kombinatorischen Hintergrund, dass das so
> geht. Nur welchen genau?
Nun, das [mm] c_k [/mm] zählt doch genau, auf wie viele Weisen das k als Summe von Exponenten aus den einzelnen Faktoren gebildet werden kann.
Gruß
Dieter
|
|
|
| |
|
> Nun, das [mm]c_k[/mm] zählt doch genau, auf wie viele Weisen das k
> als Summe von Exponenten aus den einzelnen Faktoren
> gebildet werden kann.
Ist zwar schon etwas her, aber ich hatte die Woche leider wenig Zeit reinzuschauen.
Könntest du bzw. irgendjemand das nochmal mit anderen Worten erklären? Ich verstehe das noch nicht so ganz. Ich habe mich gerade etwas mit den Catalan-Zahlen beschäftigt, wovon die vorliegende Aufgabe anscheinend ein Teilgebiet ist, aber so wirklich durchsteigen tue ich da noch nicht.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:20 Mo 22.06.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
