Rekursion und Kombinatorik < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe 1 | | Wie viele mögliche Buchstabenanordnungen kann man aus A,B,C,D,E,F bilden, sodass B niemals auf A folgt, C niemals auf B, ... F niemals auf E. |
| Aufgabe 2 | Gegeben sei folgende Rekursion:
[mm] a_n=\frac{1}{2}\left(\frac{2^n}{n!}-\summe a_k*a_{n-k}\right)
[/mm]
Geben Sie die explizite Darstellung von [mm] a_n [/mm] an.
Hinweis: Verwenden Sie die Reihendarstellung von [mm] e^z [/mm] |
Hallo!
Ich weiß bei beiden Beispielen nicht wirklich weiter.
Meine Ansätze:
1) Wir hatten ein ähnliches Beispiel, bei dem man die Zahl [mm] 1\leq [/mm] k [mm] \leq [/mm] n nur plazieren darf in einem Tupel, (außer natürlich beim ersten), wenn k-1 oder k+1 schon plaziert worden ist. Da sind wir auf k-1 über n-1 gekommen. Aber ich weiß nicht, ob und wie man das hier adaptieren kann.
2) Mein Rechenvorgang (wir haben eigentlich nur lineare Rekursionen mit konstanten Koeffizienten gemacht und formale Potenzreihen, also jegliche andere Ansätze sollten nicht verwendet werden):
[mm] a_n=\frac{1}{2}(\frac{2^n}{n!}-\summe a_k*a_{n-k}) [/mm] mit [mm] z^n [/mm] multiplizieren und über [mm] n\geq [/mm] 0 aufsummieren.
also [mm] \summe_{n\geq 0} a_n*z^n=\summe_{n\geq 0}\frac{1}{2}\left(\frac{2^n}{n!}-\summe a_k*a_{n-k}\right)z^n
[/mm]
Dann nenne ich mal die erzeugende Funktion G(z) = [mm] \summe_{n \geq0} a_n z^n.
[/mm]
Also habe ich:
G(z) = [mm] \summe_{n\geq 0}\frac{1}{2}\left(\frac{2^n}{n!}-\summe a_k*a_{n-k}\right)z^n
[/mm]
wobei [mm] \summe_{n\geq 0} \frac{2^n}{n!}z^n [/mm] = [mm] e^{2z} [/mm] und [mm] \summe_{n\geq 0} \summe a_k*a_{n-k}z^n [/mm] = [mm] G(z)^2 [/mm] ist.
Also
G(z) = [mm] \frac{1}{2} \left(e^{2z} - G(z)^2\right)
[/mm]
[mm] G(z)^2+2G(z)-e^{2z} [/mm] = 0
und jetzt würde ich einfach mal die quadratische Gleichung lösen:
[mm] G_{1,2}(z)=\frac{-2\pm\wurzel{4+4e^{2z}}}{2}=-1\pm\wurzel{1+e^{2z}}
[/mm]
und jetzt - Reihenentwicklung der Wurzel und [mm] e^z? [/mm] Wie komme ich dann auf die Koeffizienten von [mm] z^n, [/mm] die mir ja dann mein [mm] a_n [/mm] explizit ausdrücken?
Weiters ist [mm] a_0=1 [/mm] gegeben, aber bei dem bin ich mir nicht so sicher, kann auch falsch abgetippt sein...
Vielen Dank im Voraus!
|
|
| |
|
> Wie viele mögliche Buchstabenanordnungen kann man aus
> A,B,C,D,E,F bilden, sodass B niemals auf A folgt, C niemals
> auf B, ... F niemals auf E.
Gemeint (aber nicht ausdrücklich gesagt) ist wohl, dass
jeweils jeder der 6 Buchstaben genau einmal vorkommen
soll. Stünde da anstelle von "Buchstabenanordnungen"
der Fachausdruck "Permutationen", so wäre es klar.
Mir würde die Frage übrigens etwas besser gefallen,
falls da zusätzlich noch stünde "... A niemals auf F ..."
> Gegeben sei folgende Rekursion:
> [mm]a_n=\frac{1}{2}\left(\frac{2^n}{n!}-\summe a_k*a_{n-k}\right)[/mm]
> Geben Sie die explizite Darstellung von [mm]a_n[/mm] an.
> Hinweis: Verwenden Sie die Reihendarstellung von [mm]e^z[/mm]
Bei der Summe fehlen die Summationsgrenzen.
Und: sind für die [mm] a_k [/mm] keinerlei Anfangswerte vorgegeben ?
LG Al-Chw.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 00:20 Fr 02.03.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
