Дерево Калкина

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

Дерево Ка́лкина — Уи́лфа (англ. Calkin—Wilf tree) — ориентированное двоичное дерево, в вершинах которого расположены положительные рациональные дроби согласно следующему правилу:

• корень дерева — дробь  $\frac11\!$;
• вершина с дробью  $\frac mn\!$ имеет двух потомков: $\frac m{m+n}\!$ (левый) и $\frac{m+n}n\!$ (правый).

Дерево описано Нейлом Калкином и Гербертом С. Уилфом (2000^[1]) в связи с задачей явного пересчёта^[2] множества рациональных чисел.

Свойства дерева Калкина — Уилфа

Основные свойства

• Все дроби, расположенные в вершинах дерева, несократимы;
• Любая несократимая рациональная дробь встречается в дереве в точности один раз.

Последовательность Калкина — Уилфа

Обход «сначала-в-ширину» дерева Калкина — Уилфа (путь обхода показан розовой спиралью)

Из приведенных выше свойств следует, что последовательность положительных рациональных чисел, получаемая в результате обхода «сначала-в-ширину»^[3] (англ. breadth-first traversal) дерева Калкина — Уилфа (называемая также последовательностью Калкина — Уилфа; см. иллюстрацию):

$\frac11, \frac12, \frac21, \frac13, \frac32, \frac23, \frac31, \frac14, \frac43, \frac35, \frac52, \frac25, \frac53, \frac34, \dots,\!$

определяет взаимно однозначное соответствие между множеством натуральных чисел и множеством положительных рациональных чисел.

Данная последовательность может быть задана рекуррентным соотношением^[4]:

$q_1=1;\!$

$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\!,$

где $\lfloor x\rfloor$ и $\{x\}$ обозначают соответственно целую и дробную части числа $x$.

В последовательности Калкина — Уилфа знаменатель каждой дроби равен числителю следующей.

Функция fusc

В 1976 году Э. Дейкстра определил на множестве натуральных чисел целочисленную функцию fusc(n) следующими рекуррентными соотношениями^[5]:

• $\mathop{\mathrm{fusc}}(1)=1$;
• $\mathop{\mathrm{fusc}}(2n)=\mathop{\mathrm{fusc}}(n)$;
• $\mathop{\mathrm{fusc}}(2n+1)=\mathop{\mathrm{fusc}}(n) + \mathop{\mathrm{fusc}}(n+1)$.

Последовательность значений $\scriptstyle{\mathop{\mathrm{fusc}}(n),\ n=1,2,3,\dots}$, совпадает с последовательностью числителей дробей в последовательности Калкина — Уилфа, то есть последовательностью

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

Таким образом (поскольку знаменатель каждой дроби в последовательности Калкина — Уилфа равен числителю следующей), $n$-ый член последовательности Калкина — Уилфа равен $\scriptstyle{\mathop{\mathrm{fusc}}(n)/\mathop{\mathrm{fusc}}(n+1)}$, а соответствие

$n\mapsto\frac{\mathop{\mathrm{fusc}}(n)}{\mathop{\mathrm{fusc}}(n+1)},\quad n=1,2,3,\dots$

является взаимно однозначным соответствием между множеством натуральных чисел и множеством положительных рациональных чисел.

Функция $\scriptstyle{\mathop{\mathrm{fusc}}}$ может быть, помимо указанных выше рекуррентных соотношений, определена следующим образом.

• Значение $\scriptstyle{\mathop{\mathrm{fusc}}}(n+1),\ n\geqslant0,$ равно количеству гипердвоичных (англ. hyperbinary) представлений числа $n$, то есть представлений в виде суммы неотрицательных степеней двойки, где каждая степень $2^k$ встречается не более двух раз^[6]. Например, число 6 представляется тремя такими способами:

6 = 4 + 2 = 4 + 1 + 1 = 2 + 2 + 1 + 1, поэтому $\scriptstyle{\mathop{\mathrm{fusc}}}(6+1)=3$.

• Значение $\scriptstyle{\mathop{\mathrm{fusc}}(n+1)},\ n\geqslant0,$ равно числу всех нечётных биномиальных коэффициентов вида $\scriptstyle {n-r\choose r}$, где $\scriptstyle{0\leqslant 2r<n}$^[7].

В оригинальной статье Калкина и Уилфа функция $\scriptstyle{\mathop{\mathrm{fusc}}}$ не упоминается, но рассматривается целочисленная функция $b(n)$, определённая для $\scriptstyle n=0,1,2,\dots$, равная количеству гипердвоичных представлений числа $n$ и доказывается, что соответствие

$n\mapsto\frac{b(n)}{b(n+1)},\quad n=0,1,2,\dots,\!$

является взаимно однозначным соответствием между множеством неотрицательных целых чисел и множеством рациональных чисел. Таким образом, для $\scriptstyle n=0,1,2,\dots$ имеют место соотношения:

• $\scriptstyle b(n)=\mathop{\mathrm{fusc}}(n+1);$
• $\scriptstyle b(2n+1)=b(n);\quad b(2n+2)=b(n)+b(n+1).\!$

Дерево Кеплера и Saltus Gerberti

«Гармония мира» И. Кеплера (1619), книга III (фрагмент)

Этот раздел статьи ещё не написан. Согласно замыслу одного из участников Википедии, на этом месте должен располагаться специальный раздел. Вы можете помочь проекту, написав этот раздел.

Примечания

1. ↑ См. статью Calkin, Wilf (2000) в списке литературы.
2. ↑ То есть явного задания взаимно однозначного соответствия между множеством натуральных чисел и множества (положительных) рациональных чисел. Стандартные доказательства счётности множества рациональных чисел обычно не используют явное задание указанного соответствия.
3. ↑ В данном случае обход «сначала-в-ширину» соответствует последовательному обходу каждого уровня (начиная с верхнего) дерева Калкина — Уилфа слева направо (см. первую иллюстрацию).
4. ↑ Найдено Моше Ньюменом (Moshe Newman); см. книгу Айгнера и Циглера в списке литературы, с. 108
5. ↑ Документ EWD 570: An exercise for Dr.R.M.Burstall; воспроизведен в книге Dijkstra (1982) (см. список литературы), pp. 215—216.
6. ↑ При этом считается, что число $0$ обладает единственным («пустым») гипердвоичным представлением $0=0$, поэтому $\scriptstyle\mathop{\mathrm{fusc}}(0+1)=1$.
7. ↑ См. Carlitz, L. A problem in partitions related to the Stirling numbers // Bulletin of the American Mathematical Society. — 1964. — Vol. 70. — № 2. — P. 275—278. В этой статье определяется функция $\theta_0(n)$, которая оказывается связанной с функцией fusc соотношением $\theta_0(n)$=fusc(n+1).

Литература

• Calkin, N., Wilf H. S. Recounting the Rationals // The American Mathematical Monthly. — 2000. — Vol. 107. — № 4. — P. 360—363. (JSTOR 2589182)
• Айгнер М., Циглер Г. Доказательства из Книги. Лучшие доказательства со времён Евклида до наших дней (пер. с англ.). — М.: Мир, 2006. — С. 105—109. — 256 с. — ISBN 5-03-003690-3. (NB: в данном переводе фамилия Wilf транскрибируется как «Вилф».)
• Dijkstra, E. W. Selected Writings on Computing: A Personal Perspective. — Springer-Verlag, 1982. — ISBN 0-387-90652-5. (См. документы EWD 570 и EWD 578, воспроизведенные в этой книге.)
• Stern M. Über eine zahlentheoretische Funktion // Journal für die reine und angewandte Mathematik. — 1858. — Т. 55. — С. 193—220.
• Щетников А. И. Алгоритм разворачивания всех числовых отношений из отношения равенства и идеальные числа Платона // ΣΧΟΛΗ. — 2008. — Т. 2. — С. 55—74. — ISSN 1995-4328.

См. также

• Дерево Штерна — Броко