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

Дерево Штерна–Броко и последовательности Штерна–Броко порядка i для i = 1, 2, 3, 4

В теории чисел дерево Штерна -Броко представляет собой бесконечное полное двоичное дерево , в котором вершины соответствуют один к одному положительным , рациональным числам значения которых упорядочены слева направо, как в дереве поиска .

Дерево Штерна-Броко было введено независимо Морицем Штерном ( 1858 г. ) и Ахиллом Броко ( 1861 г. ). Штерн был немецким теоретиком чисел; Броко был французским часовщиком , который использовал дерево Штерна-Броко для проектирования систем зубчатых колес с передаточным числом, близким к некоторому желаемому значению, путем нахождения соотношения гладких чисел вблизи этого значения.

Корень дерева Штерна-Броко соответствует числу 1. Отношение родитель-потомок между числами в дереве Штерна-Броко может быть определено в терминах непрерывных дробей или медиан , а также пути в дереве от корня к любому другому число q обеспечивает последовательность приближений к q с меньшими знаменателями , чем q . Поскольку дерево содержит каждое положительное рациональное число ровно один раз, поиск в ширину дерева обеспечивает метод перечисления всех положительных рациональных чисел, который тесно связан с последовательностями Фарея . Левое поддерево дерева Штерна–Броко, содержащее рациональные числа в диапазоне (0,1), называется деревом Фарея .

Создание правила

Каждой вершине в дереве можно сопоставить тройку дробей, состоящую из трех дробей в той же строке, что и вершина, а именно дроби непосредственно слева от вершины, дроби в самой вершине и дроби непосредственно справа. вершины. (См. рисунок выше.) Левая и правая дроби соответствуют не вершинам в той же строке, что и вершина, а скорее вершинам в некоторой предыдущей строке. Каждую такую ​​дробь можно понимать как метку области плоскости, ограниченной двумя бесконечными путями, спускающимися из предыдущей вершины, помеченной той же дробью. Второй элемент тройки всегда будет медиатой первого и третьего элементов. Например, корень связан с $\left({\tfrac {0}{1}},{\tfrac {1}{1}},{\tfrac {1}{0}}\right)$ и его левые и правые потомки связаны с $\left({\tfrac {0}{1}},{\tfrac {1}{2}},{\tfrac {1}{1}}\right)$ и $\left({\tfrac {1}{1}},{\tfrac {2}{1}},{\tfrac {1}{0}}\right)$. Дерево генерируется по следующему правилу: левый потомок $\left({\tfrac {a}{b}},{\tfrac {c}{d}},{\tfrac {e}{f}}\right)$ является $\left({\tfrac {a}{b}},{\tfrac {a+c}{b+d}},{\tfrac {c}{d}}\right)$ и правый потомок $\left({\tfrac {c}{d}},{\tfrac {c+e}{d+f}},{\tfrac {e}{f}}\right)$.

Дерево цепных дробей

Отношения между родителями и потомками также можно понимать в терминах цепных дробей. Каждое положительное рациональное число $q$ может быть выражено как непрерывная дробь формы $$q=a_{0}+{\cfrac {1}{a_{1}+{\cfrac {1}{a_{2}+{\cfrac {1}{a_{3}+{\cfrac {1}{\ddots +{\cfrac {1}{a_{k}}}}}}}}}}}=[a_{0};a_{1},a_{2},\ldots ,a_{k}]$$где $k$ и $a_{0}$ являются целыми неотрицательными числами, и каждый последующий коэффициент $a_{i}$ является положительным целым числом. Это представление не является единственным, поскольку $$[a_{0};a_{1},a_{2},\ldots ,a_{k-1},1]=[a_{0};a_{1},a_{2},\ldots ,a_{k-1}+1],$$но использование этой эквивалентности для замены каждой цепной дроби, заканчивающейся единицей, на более короткую цепную дробь показывает, что каждое рациональное число имеет уникальное представление, в котором последний коэффициент больше единицы. Тогда, если только $q=1$, число $q$ имеет родителя в дереве Штерна – Броко, заданном выражением цепной дроби $$[a_{0};a_{1},a_{2},\ldots ,a_{k}-1].$$ Эквивалентно, этот родительский элемент формируется путем уменьшения знаменателя в самом внутреннем члене непрерывной дроби на 1 и сокращения с предыдущим членом, если дробь становится ${\tfrac {1}{1}}$. Например, рациональное число 23 ⁄ 16 имеет представление цепной дроби. $${\frac {23}{16}}=1+{\cfrac {1}{2+{\cfrac {1}{3+{\frac {1}{2}}}}}}=[1;2,3,2],$$ поэтому его родителем в дереве Штерна – Броко является число $$[1;2,3,1]=[1;2,4]=1+{\cfrac {1}{2+{\frac {1}{4}}}}={\frac {13}{9}}.$$

И наоборот, каждое число $q$ в дереве Штерна–Броко имеет ровно два потомка: если $$q=[a_{0};a_{1},a_{2},\ldots ,a_{k}]=[a_{0};a_{1},a_{2},\ldots ,a_{k}-1,1]$$тогда один дочерний элемент - это число, представленное цепной дробью $$\displaystyle [a_{0};a_{1},a_{2},\ldots ,a_{k}+1]$$ в то время как другой ребенок представлен непрерывной дробью $$[a_{0};a_{1},a_{2},\ldots ,a_{k}-1,2].$$ Один из этих детей младше $q$ и это левый ребенок; другой больше, чем $q$ и это правый дочерний элемент (на самом деле первое выражение дает левого дочернего элемента, если $k$ нечетный и правильный ребенок, если $k$ четный).Например, представление цепной дроби 13 ⁄ 9 — это [1;2,4], а его два дочерних элемента — [1;2,5] = 16 ⁄ 11 (правый ребенок) и [1;2,3,2] = 23/16 . ( левый ребенок)

Ясно, что для каждого выражения конечной цепной дроби можно неоднократно переходить к его родителю и достигать корня [1;]= 1 ⁄ 1 дерева за конечное число шагов ( + _{за 0} ... + a _k - 1 точнее, шагов). Следовательно, каждое положительное рациональное число встречается в этом дереве ровно один раз. Более того, все потомки левого дочернего элемента любого числа q меньше q , а все потомки правого дочернего элемента q больше q . Числа на глубине d в дереве — это числа, для которых сумма коэффициентов цепной дроби равна d + 1 .

Медианты и бинарный поиск

Дерево Штерна – Броко образует бесконечное двоичное дерево поиска относительно обычного порядка рациональных чисел. Набор рациональных чисел, спускающихся из узла q, определяется открытым интервалом ( L _q , H _q ), где L _q — предок числа q , меньшего, чем q, и ближайшего к нему в дереве (или L _q = 0, если q не имеет меньшего предка), а H _q — предок q, который больше q и ближайший к нему в дереве (или H _q = +∞, если q не имеет большего предка).

Путь от корня 1 до числа q в дереве Штерна – Броко можно найти с помощью алгоритма двоичного поиска , который можно выразить простым способом с помощью медиан . Дополните неотрицательные рациональные числа, включив в них значение 1/0 (представляющее +∞), которое по определению больше, чем все остальные рациональные числа. Алгоритм двоичного поиска работает следующим образом:

• Инициализируйте два значения L и H значениями 0/1 и 1/0 соответственно.
• Пока q не будет найден, повторяйте следующие шаги:
  • Пусть L = a / b и H = c / d ; вычислите медиану M = ( a + c )/( b + d ).
  • Если M меньше q , то q находится в открытом интервале ( M , H ); замените L на M и продолжайте.
  • Если M больше, чем q , то q находится в открытом интервале ( L , M ); замените H на M и продолжайте.
  • В остальном случае q = M ; завершить алгоритм поиска.

Последовательность значений M, вычисленная в результате этого поиска, представляет собой в точности последовательность значений на пути от корня до q в дереве Штерна – Броко. Каждый открытый интервал ( L , H то шаге поиска, представляет собой интервал ( , _, HM ) _{), встречающийся на каком -} представляющий потомков медианы M. LM Родителем q в дереве Штерна-Броко является последний найденный медиант, не равный q .

Эту процедуру двоичного поиска можно использовать для преобразования чисел с плавающей запятой в рациональные числа. Остановившись после достижения желаемой точности, числа с плавающей запятой можно аппроксимировать до произвольной точности. Если действительное число x приближается любым рациональным числом a / b , которого нет в последовательности медиан, найденной алгоритмом выше, то последовательность медиан содержит более близкое приближение к x , имеющее знаменатель, не более чем равный b ; в этом смысле эти медианы образуют наилучшие рациональные приближения к x .

Дерево Штерна-Броко само по себе может быть определено непосредственно через медианы: левый дочерний элемент любого числа q является медиатой q с его ближайшим меньшим предком, а правый дочерний элемент q является медиантой q с его ближайшим большим предком. В этой формуле q и его предок должны быть взяты в наименьших значениях, и если нет меньшего или большего предка, то следует использовать 0/1 или 1/0 соответственно. Опять же, используя в качестве примера 7/5, его ближайший меньший предок — 4/3, поэтому его левый дочерний элемент — (4 + 7)/(3 + 5) = 11/8, а его ближайший больший предок — 3/2, поэтому его правый дочерний элемент равен (7 + 3)/(5 + 2) = 10/7.

Связь с последовательностями Фарея

Последовательность Фарея порядка n — это отсортированная последовательность дробей в замкнутом интервале [0,1], знаменатель которых меньше или равен n . Как и в методе двоичного поиска для создания дерева Штерна – Броко, последовательности Фарея могут быть построены с использованием медиан: последовательность Фарея порядка n + 1 формируется из последовательности Фари порядка n путем вычисления медианы каждых двух последовательных значений в последовательность Фарея порядка n , сохраняя подмножество медиан, знаменатель которых точно равен n + 1, и помещая эти медианы между двумя значениями, из которых они были вычислены.

Аналогичный процесс вставки медианты, начинающийся с другой пары конечных точек интервала [0/1,1/0], также можно рассматривать для описания построения вершин на каждом уровне дерева Штерна – Броко. Последовательность Штерна-Броко порядка 0 представляет собой последовательность [0/1,1/0], а последовательность Штерна-Броко порядка i представляет собой последовательность, образованную путем вставки медианты между каждой последовательной парой значений в последовательности Штерна-Броко. порядка i − 1. Последовательность Штерна–Броко порядка i состоит из всех значений на первых i уровнях дерева Штерна–Броко вместе с граничными значениями 0/1 и 1/0 в числовом порядке.

Таким образом, последовательности Штерна-Броко отличаются от последовательностей Фэрея двумя способами: они в конечном итоге включают все положительные рациональные числа, а не только рациональные числа в интервале [0,1], и на n -м шаге включаются все медианы, а не только те, которые со знаменателем, равным n . Последовательность Фарея порядка n может быть найдена путем обхода левого поддерева дерева Штерна – Броко по порядку с возвратом всякий раз, когда число со знаменателем, большим n достигается .

Дополнительные свойства

Если ${{\frac {p_{1}}{q_{1}}},{\frac {p_{2}}{q_{2}}},\dots ,{\frac {p_{n}}{q_{n}}}}$ все рациональные числа находятся на одной и той же глубине в дереве Штерна – Броко, тогда

$\sum _{k=1}^{n}{\frac {1}{p_{k}q_{k}}}=1$.

Более того, если ${{\frac {p}{q}}<{\frac {p'}{q'}}}$ две последовательные дроби на определенном уровне дерева или выше (в том смысле, что любая дробь между ними должна находиться на более низком уровне дерева), тогда

$p'q-pq'=1$.

Наряду с определениями в терминах непрерывных дробей и медиан, описанными выше, дерево Штерна – Броко также можно определить как декартово дерево для рациональных чисел с приоритетом по их знаменателям. Другими словами, это уникальное двоичное дерево поиска рациональных чисел, в котором родительский элемент любой вершины q имеет меньший знаменатель, чем q (или если q и его родительский элемент являются целыми числами, в которых родительский элемент меньше q ). Из теории декартовых деревьев следует, что наименьшим общим предком любых двух чисел q и r в дереве Штерна–Броко является рациональное число в замкнутом интервале [ q , r ], которое имеет наименьший знаменатель среди всех чисел в этом интервале. .

Перестановка вершин на каждом уровне дерева Штерна-Броко с помощью перестановки битов дает другое дерево, дерево Калкина-Уилфа , в котором дочерними элементами каждого числа a / b являются два числа a /( a + b ). и ( а + б )/ б . Как и дерево Штерна-Броко, дерево Калкина-Уилфа содержит каждое положительное рациональное число ровно один раз, но это не бинарное дерево поиска.

См. также

• Функция вопросительного знака Минковского , определение которой для рациональных аргументов тесно связано с деревом Штерна – Броко.
• Дерево Калкина – Уилфа

Ссылки

• Броко, Ахилл (1861), «Расчет шестерен методом приближения, новый метод», Revue Chronométrie , 3 : 186–194 .
• Броко, Ахилл (1862 г.), «Расчет шестерен методом аппроксимации, новый метод», https://gallica.bnf.fr/ark:/12148/bpt6k1661912?rk=21459;2
• Стерн, Мориц А. (1858), «О теоретико-числовой функции» , Журнал чистой и прикладной математики , 55 : 193–220 .
• Берстель, Жан; Лауве, Аарон; Ройтенауэр, Кристоф; Салиола, Франко В. (2009), Комбинаторика слов. Слова Кристоффеля и повторы в словах , Серия монографий CRM, том. 27, Провиденс, Род-Айленд: Американское математическое общество , ISBN.  978-0-8218-4480-9 , Збл   1161.68043

Внешние ссылки

• Айлам, Дхрува (2013), Модифицированные последовательности Штерна-Броко , arXiv : 1301.6807 , Бибкод : 2013arXiv1301.6807A
• Остин, Дэвид, Деревья, Зубы и Время: Математика изготовления часов , Тематическая колонка от AMS
• Богомольный, Александр , Штерн Броко-Три , разрезанный узел , получено 3 сентября 2008 г.
• Слоан, NJA , Дерево Стерна-Броко или Фарея , Интернет-энциклопедия целочисленных последовательностей .
• Вильдбергер, Норман, MF96: Дроби и дерево Штерна-Броко .
• Вайсштейн, Эрик В. , «Дерево Штерна – Броко» , MathWorld
• Дерево Штерна – Броко в PlanetMath .
• Бесконечные дроби , Числофил
• Удивительные графики III , числофил
• Последовательность OEIS A002487 (двуатомная серия Стерна (или последовательность Штерна-Броко))