Дерево Штерна — Броко

Дерево Штерна — Броко — спосіб розташування всіх невід'ємних нескоротних дробів у вершинах упорядкованого нескінченного двійкового дерева.

У кожному вузлі дерева Штерна — Броко (іноді також званого деревом Фарея) стоїть медіанта ${\displaystyle {\frac {m+m'}{n+n'}}}$ дробів ${\displaystyle {\frac {m}{n}}}$ і ${\displaystyle {\frac {m'}{n'}}}$, які стоять у найближчих до цього вузла лівому і правому верхніх вузлах. Початковий шматок дерева Штерна — Броко в цьому випадку має такий вигляд:

Близьким за побудовою до дерева Штерна — Броко є дерево Калкіна — Вілфа, в якому дріб ${\displaystyle {\frac {1}{1}}}$ є коренем, а всі інші вузли заповнюються за таким алгоритмом: кожна вершина ${\displaystyle {\frac {m}{n}}}$ має двох нащадків: лівого ${\displaystyle {\frac {m}{m+n}}}$ і правого ${\displaystyle {\frac {m+n}{n}}}$.

Історія

У книзі Р. Грема, Д. Кнута, «» відкриття «дерева Штерна — Броко» пов'язується з іменами (1858) і (1860). Однак аналогічна побудова у формі «дерева Калкіна — Вілфа» була відомою ще давньогрецьким математикам. Його описана під назвою «породження всіх відношень з відношення рівності як з матері і кореня» в двох математичних оглядах II століття, що належать Нікомаху Гераському і ^[ru]. Теон повідомляє, що ця конструкція була відома Ератосфену Киренському — знаменитому вченому, що жив у III столітті до н. е.

Властивості

• Всі дроби в деревах Калкіна — Вілфа і Штерна — Броко нескоротні;
• Кожен нескоротний дріб з'являється в дереві рівно один раз.

Для дерева Калкіна — Вілфа ці властивості легко довести, якщо зауважити, що кожному кроку деревом у напрямку до кореня відповідає елементарний крок віднімання меншого числа з більшого в алгоритмі Евкліда для пошуку найбільшого спільного дільника.

Для дерева Штерна — Броко доведення ґрунтується на такій лемі: якщо ${\displaystyle p_{1}/q_{1}<p_{2}/q_{2}}$ — дроби в двох сусідніх вузлах дерева, то ${\displaystyle q_{1}p_{2}-q_{2}p_{1}=1}$.

Система числення Штерна — Броко

Можна скористатися символами L і R для ідентифікації лівої і правої гілки при просуванні вниз по дереву від кореня, дробу 1/1, до деякого певного дробу. Тоді кожен додатний дріб отримує єдине подання у вигляді рядка, що складається зі символів «R» і «L» (дробу 1/1 відповідає порожній рядок). Таке подання додатних раціональних чисел назвемо системою числення Штерна — Броко. Наприклад, позначення LRRL відповідає дробу 5/7.

Див. також

• Ряд Фарея
• Ланцюговий дріб
• Система числення
• Алгоритм Евкліда
• Дерево Калкіна — Вілфа
• Коло Форда

Література

• , Циглер Г. Доказательства из Книги. Лучшие доказательства со времён Евклида до наших дней. — М. : Мир, 2006. — С. 105—109. — ..
• Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики. — М. : Мир, 1998. — 704 с. — ..
• Щетников А. И. Алгоритм разворачивания всех числовых отношений из отношения равенства и идеальные числа Платона // . — 2008. — Т. 2 (18 червня). — С. 55—74. — ISSN 1995-4328. з джерела 5 лютого 2020. Процитовано 29 червня 2021.
• Brocot A. Calcul des rouages par approximation, nouvelle méthode // Revue Chonométrique. — 1861. — Т. 3 (18 червня). — С. 186—194.
• Stern M. Über eine zahlentheoretische Funktion // Journal für die reine und angewandte Mathematik. — 1858. — Т. 55 (18 червня). — С. 193—220.

Посилання

• The Stern — Brocot or Farey Tree [ 24 жовтня 2010 у Wayback Machine.](англ.)
• Кноп К. Недвоичная система // Домашний компьютер. — 2001. — № 8 (18 червня). з джерела 12 березня 2007.
• Онлайн-демонстратор наближення раціональних чисел за допомогою дерева Штерна — Броко [ 29 червня 2021 у Wayback Machine.]