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

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

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

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

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

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

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

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

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

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

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

$\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},i=1,2,\dots ,$

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

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

Функция fusc

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

См. также

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

Литература

• Шаблон:Статья (JSTOR 2589182)
• Шаблон:Книга (NB: в данном переводе фамилия Wilf транскрибируется как «Вилф».)
• Шаблон:Книга (См. документы EWD 570 и EWD 578, воспроизведенные в этой книге.)
• Шаблон:Статья
• Шаблон:Статья