Rekursion gesucht

20.01.2007, 17:38	anka1	Auf diesen Beitrag antworten »
Rekursion gesucht Hallo, ich hab eine Aufgabe gelöst und wollt man fragen ob diese Lösung richtig ist: Aufgabe: Ich soll die Anzahl der linearen Anordnungen der Zahlen von 1 bis n finden, so dass jede Zahl höchstens eine Stelle von ihrer Position in der Standartanordnung 1 - 2 - ... - n entfernt ist. Dazu soll man eine Rekursionsgleichung aufstellen und die dann lösen.. Hab mir überlegt das man im Prinzip nur die benachbarten Zahlen vertauschen darf und komme auf die Rekursionsgleichung: $\begin{eqnarray} a_n = a_{n-1} + a_{n-2} \end{eqnarray}$ quasi die Fibonaccifolge, allerdings mit x grösser 2 und $\begin{eqnarray} a_0=1;a_1=1 \end{eqnarray}$ und komme auf eine geschlossene form: $\begin{eqnarray} a_n = c_1\lambda_1 + c_2\lambda_2 \end{eqnarray}$ mit $\begin{eqnarray} \lambda_1 = \frac{1+\sqrt{5}}{2} \end{eqnarray}$ $\begin{eqnarray} \lambda_2 = \frac{1-\sqrt{5}}{2} \end{eqnarray}$ $\begin{eqnarray} c_1 = -\frac{1}{2\sqrt{5}} + \frac{1}{2} \end{eqnarray}$ $\begin{eqnarray} c_1 = \frac{1+\sqrt{5}}{2\sqrt{5}} \end{eqnarray}$ kann man sicher noch vereinfachen, aber scheint zu funktionieren...
20.01.2007, 18:18	AD	Auf diesen Beitrag antworten »
Im Grunde genommen meinst du das Richtige, nur folgende Anmerkungen: Was du "lineare Anordnungen" nennst, bezeichnet man treffender als "Permutationen" der Zahlen 1,2, ... , n. Der Ansatz lautet richtig $\begin{eqnarray} a_n = c_1\lambda_1^n + c_2\lambda_2^n \end{eqnarray}$ , oben hast du die Exponenten vergessen. Nicht so wichtig, aber alle Forenteilnehmer kennen meine Abneigung gegen Standart. Ansonsten ist aber alles Ok.
20.01.2007, 19:13	anka1	Auf diesen Beitrag antworten »
ja also das mit den "linearen Anordnungen " das stand so in der aufgabe drin.. stimmt ich hab das hoch n vergessen...und das eine c1 ist c2. Standard hab ich schon inner schule falsch geschrieben genauso wie das wieder oder wider...der unterschied ist mir zwar klar, aber ich machs immer wieder falsch, ich glaub das ist eine krankheit... Ich hab aber noch eine andere frage zu dieser aufgabe: Muss man da irgendwas beweisen? also ich komme durch Probieren auf die Folge...aber in der aufgabe steht nix von zeigen oder beweisen?!? Ich hab noch so eine aufgabe von der art, wo ich nicht wirklich auf die rekursionsgleichung komme, bzw. das ausprobieren ist zu umfangreich..werd die aufgaben dann mal posten..
20.01.2007, 20:43	AD	Auf diesen Beitrag antworten »
Welchen Beweis meinst du jetzt: Dass die Rekursion hier im vorliegenden Fall so gilt? Das solltest du schon beweisen. Oder meinst du, dass man aus dieser Rekursion derart die explizite Darstellung ableiten kann? Das ist eigentlich Standard, aber wenn man will, kann man abschließend die Gültigkeit der Rekursion durch vollständige Induktion nachweisen.
20.01.2007, 20:47	anka1	Auf diesen Beitrag antworten »
ja, also das die rekursion für diese aufgabe gilt.. warum und WIE muss das bewiesen werden? weil steht ja nich da, sonst stehts immer GENAU da, wenn man was beweisen soll, das macht mich immer sehr fertig nervlich...
20.01.2007, 20:55	AD	Auf diesen Beitrag antworten »
Betrachte einfach mal die letzte Stelle der Permutation, also Position $\begin{eqnarray} n \end{eqnarray}$ , für die gibtr es nur zwei Fälle... 1.Fall: Dort steht die Zahl $\begin{eqnarray} n \end{eqnarray}$ 2.Fall: Dort steht nicht die Zahl $\begin{eqnarray} n \end{eqnarray}$ ...
Anzeige

20.01.2007, 21:08	anka1	Auf diesen Beitrag antworten »
ja hmm??? also bei fall 1 stehen dann alle anderen zahlen vor n bei fall 2 muss die letzte zahl n-1 sein meinst du das??

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »