Rekursion |
| 11.01.2010, 18:09 | *Sonnenschein* | Auf diesen Beitrag antworten » | ||
| Rekursion sitze jetzt schon längere Zeit an eine Aufgabe: Auf einen Kreis gibt es 2*n Punkte. Sn sei die Anzahl der Mglichkeiten n Sehnen in den Kreis einzuspannen. Es darf keine Überschneidungen geben. Jetzt soll ich für Sn eine Rekursionsformel angeben... Hier mal meine Überlegungen: n=1 => Sn =1 (wenn ich nur eine Sehne habe, gibt es 2 Punkte und die können nur auf eine *Art* verbunden werden... n=2 => Sn =2 (und vier Punkte) n=3 => Sn = 5 (sechs Punkte) n=4 => Sn= 14 (acht Punkte) Ich weiss jetzt einfach nicht wie ich eine Formel daraus herstellen soll. Danke für jeden Tipp. |
||||
| 12.01.2010, 21:55 | wisili | Auf diesen Beitrag antworten » | ||
| RE: Rekursion Zunächst offene Fragen werden mit den angegebenen Zahlen beantwortet: Bilden die 2n Punkte ein regelmässiges n-Eck? Egal. Zählen kongruente Lösungen auch? Ja. Dürfen von einem Punkt mehrere Sehnen ausgehen? Nein, das gilt als «überschneiden». Noch ohne Antwort: Sind die angegebenen Zahlen gesichert? Sehr interessantes Problem. Heute nicht mehr ... |
||||
| 12.01.2010, 22:20 | AD | Auf diesen Beitrag antworten » | ||
Das ist eine Frage der genauen Definition von "Überschneidung" - das ist wie mit dem ungenauen Wort "zwischen". 
EDIT: Wenn es doch zugelassen wird, dann ist die Aufgabe zugegebenermaßen komplizierter. 
|
||||
| 13.01.2010, 18:44 | wisili | Auf diesen Beitrag antworten » | ||
Man findet die Lösung auch im Internet: http://www.research.att.com/~njas/sequences/A000108 Ways of joining 2n points on a circle to form n nonintersecting chords. Aus der Lösungsformel lässt sich natürlich eine Rekursion gewinnen. Aber eine Rekursion einsehen, wäre schöner. Ist mir bis jetzt nicht gelungen. |
||||
| 14.01.2010, 00:28 | Mystic | Auf diesen Beitrag antworten » | ||
"Divide et impera!" ist hier die Devise... Wenn man eine Sehne zieht, sodass zwischen den zwei Endpunkten jeweils eine gerade Zahl von Kreispunkten ist, dann hat man doch zwei Probleme von dieser Sorte für jede derartige Möglichkeit... |
||||
| 14.01.2010, 10:52 | wisili | Auf diesen Beitrag antworten » | ||
Das ist eine mutmachende Idee (mit einer Schwierigkeit: Identische Konfigurationen können mehrfach gezählt werden). Und führt wohl machbar auf eine algorithmisch-rekursive Lösung. Wir suchen aber nach EINER FOLGE (sn), die rekursiv definiert ist. Die Catalan-Zahlen liefern das schon, aber wie kann man sie geometrisch einsehen? |
||||
| Anzeige | ||||
|
|
||||
| 14.01.2010, 11:14 | Mystic | Auf diesen Beitrag antworten » | ||
Hm, wenn ich die Folgenglieder, wie in der Literatur üblich, mal mit bezeichnen darf, dann führt doch mein Vorschlag oben direkt auf die Beziehung Würdest du das nicht als Rekursion ansehen? Und die geometrische Deutung dazu habe ich ja auch oben angegeben... |
||||
| 14.01.2010, 11:26 | wisili | Auf diesen Beitrag antworten » | ||
@Mystic (Habe die Catalan-Rekursion nachgetragen, oben) Gratuliere. Ja, doch, sieht gut aus: Du schaffst es mit einer Folgen-Rekursion, die auf ALLE Vorgängerglieder zugreift. Bin aber nicht so schnell im begreifen ... Muss darüber nachdenken. |
||||
| 14.01.2010, 11:41 | Mystic | Auf diesen Beitrag antworten » | ||
Wie man deine Rekrusion geometrisch interpretieren kann, sehe ich jetzt auch nicht...Wenn überhaupt möglich, so dürfte es jedenfalls nicht einfach sein... Wie es mit mit meiner Rekursion rechnerisch weitergeht, dürfte aber klar sein... Man stellt für ihre erzeugende Funktion ausgehend von obiger Rekursion eine quadratische Gleichung auf, löst diese und kann dann aus der Lösung durch Reihenentwicklung die explizite Formel für direkt ablesen... |
||||
| 14.01.2010, 13:25 | wisili | Auf diesen Beitrag antworten » | ||
Meine Befürchtungen betreffend Mehrfachzählungen sind offenbar nicht berechtigt: Ich verstehe jetzt deine Rekursion. ACHTUNG: Es muss C0=1 heissen! Ueber die «erzeugende Funktion» müsste man, wie du meinst auf die explizite Formel kommen: Aus dieser ist es dann ein Leichtes, noch die einfache Rekursion, wie ich sie genannt habe, herzuleiten. |
||||
| 14.01.2010, 22:58 | Mystic | Auf diesen Beitrag antworten » | ||
Ja danke, hab's oben dahingehend ausgebessert... |
||||
|
|
Verwandte Themen
| Die Beliebtesten » |
| Die Größten » |
|
| Die Neuesten » |
|
