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

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

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

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

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

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

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

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

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

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

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

${\frac {1}{1}},{\frac {1}{2}},{\frac {2}{1}},{\frac {1}{3}},{\frac {3}{2}},{\frac {2}{3}},{\frac {3}{1}},{\frac {1}{4}},{\frac {4}{3}},{\frac {3}{5}},{\frac {5}{2}},{\frac {2}{5}},{\frac {5}{3}},{\frac {3}{4}},\dots$

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

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

$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) следующими рекуррентными соотношениями:

$\operatorname {fusc} (1)=1$;

$\operatorname {fusc} (2n)=\operatorname {fusc} (n)$;

$\operatorname {fusc} (2n+1)=\operatorname {fusc} (n)+\operatorname {fusc} (n+1)$.

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

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

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

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

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

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

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

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

• Значение $\operatorname {fusc} (n+1),n\geqslant 0$ равно числу всех нечётных биномиальных коэффициентов вида ${\binom {n-r}{r}}$, где $0\leqslant 2r<n$.

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

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

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

$b(n)=\operatorname {fusc} (n+1),$

$b(2n+1)=b(n),$

$b(2n+2)=b(n)+b(n+1).$

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

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

См. также

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

Литература

• 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.