Дерево Штерна — Броко — способ расположения всех неотрицательных несократимых дробей в вершинах упорядоченного бесконечного двоичного дерева .

В каждом узле дерева Штерна — Броко (иногда также называемого деревом Фарея ) стоит медианта ${\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 в. н. э., принадлежащих Никомаху Герасскому и Теону Смирнскому . Теон сообщает, что эта конструкция была известна Эратосфену Киренскому — знаменитому учёному, жившему в 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. — С. —109. — 256 с. — ISBN 5-03-003690-3 . .
• Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики. — М. : Мир, 1998. — 704 с. — ISBN 5-03-001793-3 . .
• Щетников А. И. // ΣΧΟΛΗ . — 2008. — Т. 2 . — С. 55—74 . — ISSN .
• Brocot A. Calcul des rouages par approximation, nouvelle méthode // Revue Chonométrique. — 1861. — Т. 3 . — С. 186—194 .
• Stern M. // Journal für die reine und angewandte Mathematik. — 1858. — Т. 55 . — С. 193—220 .

Ссылки

• (англ.)
• Кноп К. // Домашний компьютер. — 2001. — № 8 . 12 марта 2007 года.