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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Дерево Калкина — Уилфа

Дерево Ка́лкина — Уи́лфа (англ. 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}}} не упоминается, но рассматривается целочисленная функция 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).

Литература[править | править вики-текст]

См. также[править | править вики-текст]