Rekursive Formel für Anzahl von per. Punkten finden |
24.04.2016, 18:42 | kev04 | Auf diesen Beitrag antworten » | ||
Rekursive Formel für Anzahl von per. Punkten finden Ich habe einen Raum dessen Punkte aus unendlichen Folgen von 1en und 0en bestehen. Das für s auch dem raum gilt s=(s0s1s2s3.........) mit si=1 oder si=0. Ich schränke den Raum nun noch ein, indem keine zwei 0en aufeinander folgen dürfen, d.h. si=0 => si+1=1. Des Weiteren gibt es eine Abb f für die gilt f(s0s1s2s3....)=(s1s2s3s4......). Es wird also s0 vergessen. Zur Aufgabe: Es soll eine rekursive Formel für die Anzahl der F.P. von f^n gefunden werden, d.h. an+2 soll mit Hilfe von an+1 und an dargstellten werden, wobei an die Anzahl der F.P. von f^n ist. Meine Ideen: Ich habe mir das ganze mal für die ersten nat. Zahlen aufgeschrieben. Dabei fällt auf, dass für diese gilt an+2=an+1 +an. Es handelt sich hier also um eine (verschobene) Fibonacci-Folge. Soweit so gut. Um meine Vermutung zu beweisen bin ich wie folgt vorgegangen. Die F.P. von f^n habe die Form (s0s1s2s3.....sn-1,s0s1s2s3....sn-1,...) 1. Fall s0=1 Dann ist s1.....sn-1 Folge von 1en und 0en der Länge n-1. 2. Fall s0=0 => s1=1 und sn-1=1 s2....sn-2 ist Folge von 1en und 0en der Länge n-3. also ergibt sich an+2=an+1 + an-1 Das wollte ich aber nicht zeigen. Wo liegt mein Denkfehler? |
||||
25.04.2016, 21:01 | kev04 | Auf diesen Beitrag antworten » | ||
Hat den niemand eine Idee? |
||||
25.04.2016, 21:09 | HAL 9000 | Auf diesen Beitrag antworten » | ||
Kurz gesagt: Du suchst die Anzahl aller -stelligen Bitfolgen (bzw. zumindest eine Rekursionsformel für diese Anzahl), wo keine zwei Nullen hintereinander vorkommen, wobei das ganze "zirkulär" betrachtet wird (d.h. letzte und erste Stelle sind auch "Nachbarn") - richtig? |
||||
26.04.2016, 07:50 | HAL 9000 | Auf diesen Beitrag antworten » | ||
Ok, führen wir noch ein paar Bezeichnungen ein. ... Anzahl der -stelligen Bitfolgen ohne Übergänge 00, auch ist verboten ist die von dir eingeführte Folge, mit den Startwerten . ... Anzahl der -stelligen Bitfolgen ohne Übergänge 00 innerhalb, hier ist erlaubt ist das Äquivalent in der "linearen" Variante. Aufgrund der etwas lockereren Bedingung, was die Bitfolgenenden betrifft, sind hier die Werte mit Ausnahme von n=2 größer als bei , konkret startet diese Folge mit . Dann liegt hier
ein Trugschluss vor: Was du hier beschreibst, läuft tatsächlich auf die Formel hinaus. Mit ähnlichen Betrachtungen für wiederum bekommt man , was dann über die erste Beziehung rückwirkend auch zu führt. Mit den o.g. Startwerten stellt sich heraus, dass tatsächlich eine verschobene Fibonacci-Folge ist, nämlich . Damit ist dann - EDIT: Hallo? Erst drängeln, und dann aber trotz Vorbeischauen im Board keine Zeit für eine Reaktion? |
||||
27.04.2016, 15:09 | kev04 | Auf diesen Beitrag antworten » | ||
Entschuldige, dass ich so spät antworte, hatte keine Zeit die Aufgabe ganz zu lösen und wollte erst antworten, wenn ich die Aufgabe erneut veruscht habe. Ich danke dir sehr, dass du meinen Denkfehler gefunden hast. Hab es verstanden und habe den Beweis nun aufgestellt. |
||||
27.04.2016, 15:17 | HAL 9000 | Auf diesen Beitrag antworten » | ||
Normalerweise bin ich geduldiger. Aber diese Retourkutsche musste einfach sein. |
||||
Anzeige | ||||
|
||||
27.04.2016, 15:19 | kev04 | Auf diesen Beitrag antworten » | ||
Damit muss ich dann wohl leben. Hast mir auf jeden sehr geholfen. Woher wussten du denn, dass ich on war? |
||||
27.04.2016, 15:35 | HAL 9000 | Auf diesen Beitrag antworten » | ||
Die NSA merkt alles ... nein, im Ernst: Im Userprofil wird unter "Letzte Aktivität" der Zeitpunkt des letzten Besuches vermerkt - auch bei "nur reinschauen". |
|
Verwandte Themen
Die Beliebtesten » |
Die Größten » |
|
Die Neuesten » |
|