Drzewo Sterna-Brocota

Drzewo Sterna-Brocota – drzewo binarne zawierające wszystkie dodatnie ułamki nieskracalne.

Konstrukcja

Zaczynamy od $\frac{0}{1}$ – symbolizującego zero i $\frac{1}{0}$ symbolizującego nieskończoność. Następnie na kolejnych piętrach drzewa wpisujemy „pomiędzy” wartości $\frac{a}{b}$ oraz $\frac{c}{d}$ wartość $\frac{a+c}{b+d}$ – patrz ilustracja.

Własności

• W drzewie występują wszystkie dodatnie liczby wymierne zapisane jako ułamki nieskracalne.
• Każda liczba wymierna dodatnia występuje w drzewie dokładnie raz.
• Jeśli liczby $a$ oraz $b$ są względnie pierwsze to ułamek $\frac{a}{b}$ występuje w drzewie dokładnie raz.
• W drzewie występują wszystkie liczby dodatnie wymierne, więc taką liczbę możemy opisać jako ścieżkę od korzenia drzewa do tej liczby. Jest to skończony ciąg symboli L oraz P (albo 0 1) np. liczbę $\frac{3}{8}$ zapisujemy jako LLPL.
• Każdą liczbę rzeczywistą dodatnią możemy zapisać jako ciąg symboli L oraz P tak, że początkowe fragmenty tego ciągu symbolizują liczby wymierne przybliżające tę liczbę.

Zobacz też

• ciąg Fareya
• okrąg Forda

Linki zewnętrzne

• Szablon:MathWorld