Дерево Ка́лкина — Уи́лфа () — ориентированное двоичное дерево, в вершинах которого расположены положительные рациональные дроби согласно следующему правилу: корень дерева — дробь ; вершина с дробью имеет двух потомков: (левый) и (правый).
Дерево описано Нилом Калкином и (2000См. статью Calkin, Wilf (2000) в списке литературы.) в связи с задачей явного пересчётаТо есть явного задания взаимно однозначного соответствия между множеством натуральных чисел и множества (положительных) рациональных чисел. Стандартные доказательства счётности множества рациональных чисел обычно не используют явное задание указанного соответствия. множества рациональных чисел.
Свойства дерева Калкина — Уилфа
Основные свойства Все дроби, расположенные в вершинах дерева, несократимы; Любая несократимая рациональная дробь встречается в дереве в точности один раз.
Последовательность Калкина — Уилфа
Из приведенных выше свойств следует, что последовательность положительных рациональных чисел, получаемая в результате обхода «в ширину»В данном случае обход «в ширину» соответствует последовательному обходу каждого уровня (начиная с верхнего) дерева Калкина — Уилфа слева направо (см. первую иллюстрацию). () дерева Калкина — Уилфа (называемая также последовательностью Калкина — Уилфа; см. иллюстрацию),
определяет взаимно однозначное соответствие между множеством натуральных чисел и множеством положительных рациональных чисел.
Данная последовательность может быть задана рекуррентным соотношениемНайдено Моше Ньюменом (Moshe Newman); см. книгу Айгнера и Циглера в списке литературы, с. 108.
где и обозначают соответственно целую и дробную части числа .
В последовательности Калкина — Уилфа знаменатель каждой дроби равен числителю следующей.
Функция fusc В 1976 году Э. Дейкстра определил на множестве натуральных чисел целочисленную функцию fusc(n) следующими рекуррентными соотношениямиДокумент EWD 570: An exercise for Dr. R. M. Burstall ; воспроизведен в книге Dijkstra (1982) (см. список литературы), pp. 215—216.:
. Последовательность значений совпадает с последовательностью числителей дробей в последовательности Калкина — Уилфа, то есть последовательностью 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, …
Таким образом (поскольку знаменатель каждой дроби в последовательности Калкина — Уилфа равен числителю следующей), -й член последовательности Калкина — Уилфа равен , а соответствие
является взаимно однозначным соответствием между множеством натуральных чисел и множеством положительных рациональных чисел.
Функция может быть, помимо указанных выше рекуррентных соотношений, определена следующим образом. Значение равно количеству гипердвоичных () представлений числа , то есть представлений в виде суммы неотрицательных степеней двойки, где каждая степень встречается не более двух разПри этом считается, что число 0 обладает единственным («пустым») гипердвоичным представлением 0 = 0, поэтому .. Например, число 6 представляется тремя такими способами: 6 = 4 + 2 = 4 + 1 + 1 = 2 + 2 + 1 + 1, поэтому . Значение равно числу всех нечётных биномиальных коэффициентов вида , где См. В этой статье определяется функция , которая оказывается связанной с функцией fusc соотношением ..
В оригинальной статье Калкина и Уилфа функция не упоминается, но рассматривается целочисленная функция , определённая для , равная количеству гипердвоичных представлений числа , и доказывается, что соответствие
является взаимно однозначным соответствием между множеством неотрицательных целых чисел и множеством рациональных чисел. Таким образом, для имеют место соотношения
Дерево Кеплера и Saltus Gerberti
См. также Дерево Штерна — Броко
Примечания
Литература (JSTOR 2589182) (NB: в данном переводе фамилия Wilf транскрибируется как «Вилф».) (См. документы EWD 570 и EWD 578, воспроизведенные в этой книге.)
Категория:Алгоритмы Категория:Числа Категория:Дроби