Дерево Калкина – Уилфа

Дерево Калкина-Уилфа

Как значения извлекаются из своего родителя

В теории чисел дерево Калкина -Уилфа это дерево которого , вершины соответствуют взаимно однозначно положительным — рациональным числам . Корнем дерева является цифра 1, и любое рациональное число, проще всего выражаемое дробью $.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}Двое дочерних элементов ⁠ a / b ⁠$ — числа $⁠ а / а + б ⁠$ и $⁠ а + б / б ⁠$ . Каждое положительное рациональное число встречается в дереве ровно один раз. Он назван в честь Нила Калкина и Герберта Уилфа , но появляется и в других работах, включая Кеплера «Гармоники мира» .

Последовательность рациональных чисел при в ширину обходе дерева Калкина–Уилфа известна как последовательность Калкина–Уилфа . Его последовательность числителей (или, смещенных на единицу, знаменателей) представляет собой двухатомный ряд Штерна и может быть вычислена с помощью функции fusc .

История

Дерево Калкина-Уилфа названо в честь Нила Калкина и Герберта Уилфа , которые рассматривали его в статье 2000 года. В статье 1997 года Жан Берстель и Альдо де Лука ^{[ 1 ]} назвали то же дерево деревом Рени , поскольку некоторые идеи они почерпнули из статьи Джорджа Н. Рэйни 1973 года. ^{[ 2 ]} Двухатомный ряд Штерна был сформулирован гораздо раньше Морицем Абрахамом Штерном , немецким математиком XIX века, который также изобрел близкородственное дерево Штерна-Броко . Еще раньше подобное дерево (включающее только дроби от 0 до 1) появляется в Кеплера «Гармониях мира» (1619). ^{[ 3 ]}

Определение и структура

Дерево Калкина–Уилфа можно определить как ориентированный граф , в котором каждое положительное рациональное число $⁠ a / b ⁠$ встречается как вершина и имеет одно выходящее ребро в другую вершину, ее родителя, за исключением корня дерева, числа 1, у которого нет родителя.

Родитель любого рационального числа может быть определен после представления числа в самых простых терминах, как дробь. $⁠ a / b ⁠,$ для которого общий делитель a $b$ и $наибольший$ равен 1. Если $⁠ a / b ⁠ < 1$ , родительский элемент $⁠ а / б ⁠$ есть $⁠ а / б - а ⁠$ ; если $⁠ a / b ⁠ > 1$ , родительский элемент $⁠ а / б ⁠$ есть $⁠ а - б / б ⁠$ . Таким образом, в любом случае родителем является дробь с меньшей суммой числителя и знаменателя, поэтому повторное сокращение этого типа должно в конечном итоге достичь числа 1. Как граф с одним выходящим ребром на каждую вершину и одним корнем, достижимым всеми остальными вершинами , дерево Калкина-Уилфа действительно должно быть деревом.

Детей любой вершины в дереве Калкина – Уилфа можно вычислить путем обращения формулы для родителей вершины. Каждая вершина $⁠ a / b ⁠$ имеет одного потомка, значение которого меньше 1, $⁠ a / a + b ⁠$ , потому что, конечно, $a + b > a$ . Аналогично каждая вершина $⁠ a / b ⁠$ имеет одного потомка, значение которого больше 1, $⁠ а + б / б ⁠$ . ^{[ 4 ]}

Поскольку каждая вершина имеет двух дочерних элементов, дерево Калкина–Уилфа является бинарным деревом. Однако это не бинарное дерево поиска : его порядок не совпадает с порядком отсортировки его вершин. Однако оно тесно связано с другим бинарным деревом поиска на том же наборе вершин, деревом Штерна – Броко : вершины на каждом уровне двух деревьев совпадают и связаны друг с другом перестановкой с обращением битов . ^{[ 5 ]}

Обход в ширину

Последовательность Калкина-Уилфа - это последовательность рациональных чисел, генерируемая обходом в ширину дерева Калкина-Уилфа,

⁠ 1 1 ⁠ , ⁠ 1 2 ⁠ , ⁠ 2 1 ⁠ , ⁠ 1 3 ⁠ , ⁠ 3 2 ⁠ , ⁠ 2 3 ⁠ , ⁠ 3 1 ⁠ , ⁠ 1 4 ⁠ , ⁠ 4 3 ⁠ , ⁠ 3 5 ⁠ , ⁠ 5 2 ⁠ , ⁠ 2 5 ⁠ , ⁠ 5 3 ⁠ , ⁠ 3 4 ⁠ , ….

Поскольку дерево Калкина–Уилфа содержит каждое положительное рациональное число ровно один раз, то и эта последовательность тоже. ^{[ 6 ]} Знаменатель каждой дроби равен числителю следующей дроби в последовательности. Последовательность Калкина – Уилфа также можно сгенерировать непосредственно по формуле

q_{i+1}={\frac {1}{2\lfloor q_{i}\rfloor -q_{i}+1}}

где $q i$ обозначает $i-$ е число в последовательности, начиная с $q 1 = 1$ , а $⌊ q i ⌋$ представляет целую часть . ^{[ 7 ]}

возможно вычислить $q i$ непосредственно из кодирования длины серии двоичного представления i $:$ Также количество последовательных единиц, начиная с младшего бита, затем количество последовательных нулей, начиная с первого блока единиц, и так далее. Последовательность чисел, сгенерированная таким образом, дает в виде цепной дроби представление $q i$ . Пример:

i = 1081 = 10000111001 ₂ : Цепная дробь равна [1;2,3,4,1], следовательно,

q 1081 = ⁠ 53 / 37 ⁠

.

i = 1990 = 11111000110 ₂ : Цепная дробь равна [0;1,2,3,5], следовательно,

q 1990 = ⁠ 37 / 53 ⁠

.

В другом направлении, использование непрерывной дроби любого $q i$ в качестве кодирования двоичного числа по длине серии возвращает $само i$ . Пример:

q я = ⁠ 3/4 i ⁠ :

равна Цепная дробь [0;1,3], следовательно,

=

1110 ₂ = 14.

q я = ⁠ 4/3 [ 1 ⁠ :

— Цепная дробь ;3]. Но для использования этого метода длина цепной дроби должна быть нечетным числом . Поэтому [1;3] следует заменить эквивалентной цепной дробью [1;2,1]. Следовательно,

я

= 1001 ₂ = 9.

Аналогичное преобразование между двоичными числами, закодированными по длине серии, и непрерывными дробями также можно использовать для оценки функции вопросительного знака Минковского ; однако в дереве Калкина – Уилфа двоичные числа являются целыми числами (позиции при обходе в ширину), тогда как в функции вопросительного знака они являются действительными числами от 0 до 1.

Двухатомная последовательность Стерна

Двухатомная последовательность Стерна представляет собой целочисленную последовательность

0, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, 1, … (последовательность A002487 в OEIS ).

При нумерации, начинающейся с нуля , $n$ -е значение в последовательности — это значение $fusc(n)$ функции fusc с именем ^{[ 8 ]} в соответствии с запутанным видом последовательности значений и определяется рекуррентными отношениями

{\begin{aligned}\operatorname {fusc} (2n)&=\operatorname {fusc} (n)\\\operatorname {fusc} (2n+1)&=\operatorname {fusc} (n)+\operatorname {fusc} (n+1),\end{aligned}}

с базовыми случаями $fusc(0) = 0$ и $fusc(1) = 1$ .

n $-$ е рациональное число при обходе дерева Калкина – Уилфа в ширину — это число $⁠ fusc(n) / fusc(n + 1) ⁠$ . ^{[ 9 ]} Таким образом, двухатомная последовательность образует как последовательность числителей, так и последовательность знаменателей чисел в последовательности Калкина – Уилфа.

Функция $fusc(n + 1)$ представляет собой количество нечетных биномиальных коэффициентов вида $(п - р р)$ , $0 \leq 2 р < п$ , ^{[ 10 ]} а также подсчитывает количество способов записи $n$ как суммы степеней двойки , в которых каждая степень встречается не более двух раз. Это можно видеть из fusc, определяющего рекуррентность: выражения в виде суммы степеней двойки для четного числа $2 n$ либо не содержат в себе единиц (в этом случае они образуются путем удвоения каждого члена в выражении для $n$ ), либо двух 1s (в этом случае остальная часть выражения формируется путем удвоения каждого члена в выражении для $n - 1$ ), поэтому количество представлений представляет собой сумму количества представлений для $n$ и для $n - 1$ , что соответствует рецидив. Аналогично, каждое представление для нечетного числа $2 n + 1$ формируется путем удвоения представления для $n$ и добавления 1, что снова соответствует повторению. ^{[ 11 ]} Например,

6 = 4 + 2 = 4 + 1 + 1 = 2 + 2 + 1 + 1

имеет три представления в виде суммы степеней двойки с не более чем двумя копиями каждой степени, поэтому $fusc(6 + 1) = 3$ .

Связь с деревом Штерна – Броко

Дерево Калкина-Уилфа напоминает дерево Штерна-Броко тем, что оба являются двоичными деревьями, в которых каждое положительное рациональное число появляется ровно один раз. Кроме того, верхние уровни двух деревьев выглядят очень похожими, и в обоих деревьях одни и те же числа появляются на одних и тех же уровнях. Одно дерево можно получить из другого, выполнив перестановку битов чисел на каждом уровне деревьев. ^{[ 5 ]} Альтернативно, число в данном узле дерева Калкина-Уилфа может быть преобразовано в число в той же позиции в дереве Штерна-Броко и наоборот, с помощью процесса, включающего обращение виде цепной дроби . представлений этих чисел в ^{[ 12 ]} Однако в других отношениях они имеют разные свойства: например, дерево Штерна – Броко представляет собой двоичное дерево поиска : порядок обхода дерева слева направо такой же, как и числовой порядок чисел в нем. Это свойство неверно для дерева Калкина – Уилфа.

Примечания

^ Берстель и де Лука (1997) , Раздел 6.
^ Рэйни (1973) .
^ Кеплер, Дж. (1619), Гармоники мира , том. III, с. 27 .
^ Описание здесь двойственно исходному определению Калкина и Уилфа, которое начинается с определения дочерних отношений и выводит родительские отношения как часть доказательства того, что каждое рациональное слово появляется в дереве один раз. Как определено здесь, каждое рациональное выражение по определению появляется один раз, и вместо этого тот факт, что полученная структура является деревом, требует доказательства.
^ Перейти обратно: ^а ^б Гиббонс, Лестер и Берд (2006) .
^ Калкин и Уилф (2000) : «список всех положительных рациональных чисел, каждое из которых встречается один и только один раз, можно составить, записав ⁠ 1/1 Гиббонс ⁠ , затем дроби на уровне чуть ниже вершины дерева, читаем слева направо, затем дроби на следующем уровне вниз, читаем слева направо и т. д.» , Лестер и Бёрд ( 2006) обсуждают эффективные методы функционального программирования для выполнения этого обхода в ширину.
^ Кнут и др. (2003) приписывают эту формулу Моше Ньюману.
^ Название fusc было дано в 1976 году Эдсгером В. Дейкстрой ; см. EWD570 и EWD578.
^ Калкин и Уилф (2000) , Теорема 1.
^ Карлитц (1964) .
↑ В записи OEIS этот факт приписывают Карлитцу (1964) и нецитируемой работе Линда. Однако статья Карлитца описывает более ограниченный класс сумм степеней двойки, подсчитываемых $fusc(n)$ вместо $fusc(n + 1)$ .
^ Бейтс, Бандер и Тогнетти (2010) .

Ссылки

Айгнер, Мартин ; Циглер, Гюнтер М. (2004), Доказательства из КНИГИ (3-е изд.), Берлин; Нью-Йорк: Springer, стр. 94–97, ISBN. 978-3-540-40460-6
Бейтс, Брюс; Бандер, Мартин; Тогнетти, Кейт (2010), «Связывание деревьев Калкина-Уилфа и Штерна-Броко» , European Journal of Combinatorics , 31 (7): 1637–1661, doi : 10.1016/j.ejc.2010.04.002 , MR 2673006
Берстель, Жан; де Лука, Альдо (1997), «Слова Штурма, слова Линдона и деревья», Theoretical Computer Science , 178 (1–2): 171–203, doi : 10.1016/S0304-3975(96)00101-6
Калкин, Нил; Уилф, Герберт (2000), «Изложение рациональных оснований» (PDF) , American Mathematical Monthly , 107 (4), Математическая ассоциация Америки : 360–363, doi : 10.2307/2589182 , JSTOR 2589182 .
Карлитц, Л. (1964), «Проблема разбиений, связанная с числами Стирлинга », Бюллетень Американского математического общества , 70 (2): 275–278, doi : 10.1090/S0002-9904-1964-11118-6 , МР 0157907 .
Дейкстра, Эдсгер В. (1982), Избранные статьи о вычислительной технике: личный взгляд , Springer-Verlag , ISBN 0-387-90652-5 . EWD 570: Упражнение для доктора RMBurstall , стр. 215–216, и EWD 578: Подробнее о функции «fusc» (продолжение EWD570) , стр. 230–232, перепечатка заметок, первоначально написанных в 1976 году.
Кнут, Дональд Э.; Руперт, CP; Смит, Алекс; Стонг, Ричард (2003), «Пересчет рациональных объяснений, продолжение: 10906» , The American Mathematical Monthly , 110 (7): 642–643, doi : 10.2307/3647762 , JSTOR 3647762
Гиббонс, Джереми ; Лестер, Дэвид; Берд, Ричард (2006), «Функциональная жемчужина: перечисление рациональных чисел», Journal of Functional Programming , 16 (3): 281–291, doi : 10.1017/S0956796806005880 , S2CID 14237968 .
Рэни, Джордж Н. (1973), «О цепных дробях и конечных автоматах», Mathematische Annalen , 206 (4): 265–283, doi : 10.1007/BF01355980 , hdl : 10338.dmlcz/128216 , S2CID 120933574
Стерн, Мориц А. (1858), «О теоретико-числовой функции» , Журнал чистой и прикладной математики , 55 : 193–220 .

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

[1] Берстель и де Лука (1997) , Раздел 6.

[2] Рэйни (1973) .

[3] Кеплер, Дж. (1619), Гармоники мира , том. III, с. 27 .

[4] Описание здесь двойственно исходному определению Калкина и Уилфа, которое начинается с определения дочерних отношений и выводит родительские отношения как часть доказательства того, что каждое рациональное слово появляется в дереве один раз. Как определено здесь, каждое рациональное выражение по определению появляется один раз, и вместо этого тот факт, что полученная структура является деревом, требует доказательства.

[FOOTNOTEGibbonsLesterBird2006-5] Перейти обратно: ^а ^б Гиббонс, Лестер и Берд (2006) .

[6] Калкин и Уилф (2000) : «список всех положительных рациональных чисел, каждое из которых встречается один и только один раз, можно составить, записав ⁠ 1/1 Гиббонс ⁠ , затем дроби на уровне чуть ниже вершины дерева, читаем слева направо, затем дроби на следующем уровне вниз, читаем слева направо и т. д.» , Лестер и Бёрд ( 2006) обсуждают эффективные методы функционального программирования для выполнения этого обхода в ширину.

[7] Кнут и др. (2003) приписывают эту формулу Моше Ньюману.

[8] Название fusc было дано в 1976 году Эдсгером В. Дейкстрой ; см. EWD570 и EWD578.

[9] Калкин и Уилф (2000) , Теорема 1.

[10] Карлитц (1964) .

[11] В записи OEIS этот факт приписывают Карлитцу (1964) и нецитируемой работе Линда. Однако статья Карлитца описывает более ограниченный класс сумм степеней двойки, подсчитываемых $fusc(n)$ вместо $fusc(n + 1)$ .

[FOOTNOTEBatesBunderTognetti2010-12] Бейтс, Бандер и Тогнетти (2010) .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]