Русская Википедия:Дерево Калкина — Уилфа
Дерево Ка́лкина — Уи́лфа (Шаблон:Lang-en) — ориентированное двоичное дерево, в вершинах которого расположены положительные рациональные дроби согласно следующему правилу:
- корень дерева — дробь <math>\frac11</math>;
- вершина с дробью <math>\frac mn</math> имеет двух потомков: <math>\frac{m}{m + n}</math> (левый) и <math>\frac{m + n}{n}</math> (правый).
Дерево описано Нейлом Калкином и Шаблон:Нп5 (2000[1]) в связи с задачей явного пересчёта[2] множества рациональных чисел.
Свойства дерева Калкина — Уилфа
Основные свойства
- Все дроби, расположенные в вершинах дерева, несократимы;
- Любая несократимая рациональная дробь встречается в дереве в точности один раз.
Последовательность Калкина — Уилфа
Из приведенных выше свойств следует, что последовательность положительных рациональных чисел, получаемая в результате обхода «в ширину»[3] (Шаблон:Lang-en) дерева Калкина — Уилфа (называемая также последовательностью Калкина — Уилфа; см. иллюстрацию),
- <math>\frac11, \frac12, \frac21, \frac13, \frac32, \frac23, \frac31, \frac14, \frac43, \frac35, \frac52, \frac25, \frac53, \frac34, \dots</math>
определяет взаимно однозначное соответствие между множеством натуральных чисел и множеством положительных рациональных чисел.
Данная последовательность может быть задана рекуррентным соотношением[4]
- <math>q_1 = 1;</math>
- <math>q_{i+1} = \frac{1}{\lfloor q_i\rfloor + 1 - \{q_i\}} = \frac{1}{2\lfloor q_i\rfloor - q_i + 1}, \quad i = 1, 2, \dots,</math>
где <math>\lfloor x\rfloor</math> и <math>\{x\}</math> обозначают соответственно целую и дробную части числа <math>x</math>.
В последовательности Калкина — Уилфа знаменатель каждой дроби равен числителю следующей.
Функция fusc
В 1976 году Э. Дейкстра определил на множестве натуральных чисел целочисленную функцию fusc(n) следующими рекуррентными соотношениями[5]:
- <math>\operatorname{fusc}(1) = 1</math>;
- <math>\operatorname{fusc}(2n) = \operatorname{fusc}(n)</math>;
- <math>\operatorname{fusc}(2n + 1) = \operatorname{fusc}(n) + \operatorname{fusc}(n + 1)</math>.
Последовательность значений <math>\operatorname{fusc}(n), n = 1, 2, 3, \dots</math> совпадает с последовательностью числителей дробей в последовательности Калкина — Уилфа, то есть последовательностью
- 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, …
Таким образом (поскольку знаменатель каждой дроби в последовательности Калкина — Уилфа равен числителю следующей), <math>n</math>-й член последовательности Калкина — Уилфа равен <math>\operatorname{fusc}(n)/\operatorname{fusc}(n + 1)</math>, а соответствие
- <math>n \mapsto \frac{\operatorname{fusc}(n)}{\operatorname{fusc}(n + 1)}, \quad n = 1, 2, 3, \dots</math>
является взаимно однозначным соответствием между множеством натуральных чисел и множеством положительных рациональных чисел.
Функция <math>\operatorname{fusc}</math> может быть, помимо указанных выше рекуррентных соотношений, определена следующим образом.
- Значение <math>\operatorname{fusc}(n + 1), n \geqslant 0</math> равно количеству гипердвоичных (Шаблон:Lang-en) представлений числа <math>n</math>, то есть представлений в виде суммы неотрицательных степеней двойки, где каждая степень <math>2^k</math> встречается не более двух раз[6]. Например, число 6 представляется тремя такими способами:
- 6 = 4 + 2 = 4 + 1 + 1 = 2 + 2 + 1 + 1, поэтому <math>\operatorname{fusc}(6 + 1) = 3</math>.
- Значение <math>\operatorname{fusc}(n + 1), n \geqslant 0</math> равно числу всех нечётных биномиальных коэффициентов вида <math>\binom{n - r}{r}</math>, где <math>0 \leqslant 2r < n</math>[7].
В оригинальной статье Калкина и Уилфа функция <math>\operatorname{fusc}</math> не упоминается, но рассматривается целочисленная функция <math>b(n)</math>, определённая для <math>n = 0, 1, 2, \dots</math>, равная количеству гипердвоичных представлений числа <math>n</math>, и доказывается, что соответствие
- <math>n \mapsto \frac{b(n)}{b(n + 1)}, \quad n = 0, 1, 2, \dots</math>
является взаимно однозначным соответствием между множеством неотрицательных целых чисел и множеством рациональных чисел. Таким образом, для <math>n = 0, 1, 2, \dots</math> имеют место соотношения
- <math>b(n) = \operatorname{fusc}(n + 1),</math>
- <math>b(2n + 1) = b(n),</math>
- <math>b(2n + 2) = b(n) + b(n + 1).</math>
Дерево Кеплера и Saltus Gerberti
См. также
Примечания
Литература
- Шаблон:Статья (JSTOR 2589182)
- Шаблон:Книга (NB: в данном переводе фамилия Wilf транскрибируется как «Вилф».)
- Шаблон:Книга (См. документы EWD 570 и EWD 578, воспроизведенные в этой книге.)
- Шаблон:Статья
- Шаблон:Статья
- ↑ См. статью Calkin, Wilf (2000) в списке литературы.
- ↑ То есть явного задания взаимно однозначного соответствия между множеством натуральных чисел и множества (положительных) рациональных чисел. Стандартные доказательства счётности множества рациональных чисел обычно не используют явное задание указанного соответствия.
- ↑ В данном случае обход «в ширину» соответствует последовательному обходу каждого уровня (начиная с верхнего) дерева Калкина — Уилфа слева направо (см. первую иллюстрацию).
- ↑ Найдено Моше Ньюменом (Moshe Newman); см. книгу Айгнера и Циглера в списке литературы, с. 108.
- ↑ Документ EWD 570: An exercise for Dr. R. M. Burstall Шаблон:Wayback; воспроизведен в книге Dijkstra (1982) (см. список литературы), pp. 215—216.
- ↑ При этом считается, что число 0 обладает единственным («пустым») гипердвоичным представлением 0 = 0, поэтому <math>\operatorname{fusc}(0 + 1) = 1</math>.
- ↑ См. Шаблон:Статья В этой статье определяется функция <math>\theta_0(n)</math>, которая оказывается связанной с функцией fusc соотношением <math>\theta_0(n) = \operatorname{fusc}(n + 1)</math>.
