Дерево Штерна — Броко
Дерево Штерна — Броко — спосіб розташування всіх невід'ємних нескоротних дробів у вершинах упорядкованого нескінченного двійкового дерева.
У кожному вузлі дерева Штерна — Броко (іноді також званого деревом Фарея) стоїть медіанта дробів і , які стоять у найближчих до цього вузла лівому і правому верхніх вузлах. Початковий шматок дерева Штерна — Броко в цьому випадку має такий вигляд:
Близьким за побудовою до дерева Штерна — Броко є дерево Калкіна — Вілфа, в якому дріб є коренем, а всі інші вузли заповнюються за таким алгоритмом: кожна вершина має двох нащадків: лівого і правого .
Історія
У книзі Р. Грема, Д. Кнута, О. Паташника «Конкретна математика» відкриття «дерева Штерна — Броко» пов'язується з іменами Моріца Штерна (1858) і Ахілла Броко (1860). Однак аналогічна побудова у формі «дерева Калкіна — Вілфа» була відомою ще давньогрецьким математикам. Його описана під назвою «породження всіх відношень з відношення рівності як з матері і кореня» в двох математичних оглядах II століття, що належать Нікомаху Гераському і Шаблон:Нп. Теон повідомляє, що ця конструкція була відома Ератосфену Киренському — знаменитому вченому, що жив у III столітті до н. е.
Властивості
- Всі дроби в деревах Калкіна — Вілфа і Штерна — Броко нескоротні;
- Кожен нескоротний дріб з'являється в дереві рівно один раз.
Для дерева Калкіна — Вілфа ці властивості легко довести, якщо зауважити, що кожному кроку деревом у напрямку до кореня відповідає елементарний крок віднімання меншого числа з більшого в алгоритмі Евкліда для пошуку найбільшого спільного дільника.
Для дерева Штерна — Броко доведення ґрунтується на такій лемі: якщо — дроби в двох сусідніх вузлах дерева, то .
Система числення Штерна — Броко
Можна скористатися символами L і R для ідентифікації лівої і правої гілки при просуванні вниз по дереву від кореня, дробу 1/1, до деякого певного дробу. Тоді кожен додатний дріб отримує єдине подання у вигляді рядка, що складається зі символів «R» і «L» (дробу 1/1 відповідає порожній рядок). Таке подання додатних раціональних чисел назвемо системою числення Штерна — Броко. Наприклад, позначення LRRL відповідає дробу 5/7.