Calkin Wilf Baum < Folgen und Reihen < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 23:25 So 22.11.2009 | | Autor: | Ayame |
Ich hab mich schon informiert wie genau der calkin wilf baum aufgebaut ist :
also wir betrachten nur [mm] \IQ [/mm] größer 0 und [mm] x\in \IQ.
[/mm]
Der baum zeigt jede rationale zahl und beginnt mit [mm] \bruch{p}{q} (\bruch{1}{1}) [/mm] und hat einen linken nachfolger [mm] \bruch{p}{(p+q)} [/mm] und einen rechten nachfolger [mm] \bruch{(p+q)}{q}.
[/mm]
Ich hab die aufgaben dazu :
i) zeigen sie dass jeder bruch gekürzt ist
ii) zeigen sie dass jede positive rationale zahl vorkommt
iii) zeigen sie dass jeder gekürzte bruch genau einmal vorkommt.
und da fehlt mir einfach der ansatz. könnte mir da jemand einen tipp geben?
|
|
| |
|
> Ich hab mich schon informiert wie genau der calkin wilf
> baum aufgebaut ist :
>
> also wir betrachten nur [mm]\IQ[/mm] größer 0 und [mm]x\in \IQ.[/mm]
>
> Der baum zeigt jede rationale zahl und beginnt mit
> [mm]\bruch{p}{q} (\bruch{1}{1})[/mm] und hat einen linken nachfolger
> [mm]\bruch{p}{(p+q)}[/mm] und einen rechten nachfolger
> [mm]\bruch{(p+q)}{q}.[/mm]
>
> Ich hab die aufgaben dazu :
> i) zeigen sie dass jeder bruch gekürzt ist
> ii) zeigen sie dass jede positive rationale zahl vorkommt
> iii) zeigen sie dass jeder gekürzte bruch genau einmal
> vorkommt.
>
> und da fehlt mir einfach der ansatz. könnte mir da jemand
> einen tipp geben?
Hallo Ayame,
ich habe mich vor einiger Zeit mit dem Calkin-Wilf-Baum
und dem Stern-Brocot-Baum auseinandergesetzt, und zwar
in der Folge einer Diskussion im MatheRaum, die eigentlich
zuerst ein ganz anderes Thema hatte.
Zahlenbäume
Heute Abend ist es mir aber etwas zu spät, um auf deine
Fragen einzugehen. Ich schau mir das Ganze aber morgen
mal an.
LG Al-Chw.
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 23:46 So 22.11.2009 | | Autor: | Ayame |
Jopp die diskussion hab ich auch über google gefunden.
Leider ist sie noch etwas zu hoch für mich und hat mich nicht weitergebracht.
Aber trotzdem danke für den link :)
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 03:01 Mo 23.11.2009 | | Autor: | felixf |
Hallo!
> Jopp die diskussion hab ich auch über google gefunden.
> Leider ist sie noch etwas zu hoch für mich und hat mich
> nicht weitergebracht.
Dazu, dass jeder Bruch gekuerzt ist, machst du einfach Induktion nach der Tiefe des Bruchs im Baum. Der Bruch ganz oben ist [mm] $\frac{1}{1}$ [/mm] und somit gekuerzt. Induktionsannahme ist nun, dass alle Brueche mit der gleichen festen Tiefe $n$ gekuerzt sind. Fuer einen Bruch mit Tiefe $n + 1$ gilt, dass er entweder [mm] $\frac{p + q}{q}$ [/mm] oder [mm] $\frac{p}{p + q}$ [/mm] ist fuer einen Bruch [mm] $\frac{p}{q}$ [/mm] mit einer Tiefe $n$. Dann sind $p$ und $q$ aber teilerfremd. Zeige nun, dass dann auch $p + q, q$ und $p, p + q$ teilerfremd sind.
LG Felix
|
|
|
| |
|
Hallo Ayame,
die Antworten auf deine Fragen kannst du im
![[]](/images/popup.gif) Original-Paper
von Neil Calkin und Herbert S. Wilf finden,
allerdings natürlich in englischer Sprache.
LG Al-Chw.
|
|
|
|
