Для установки нажмите кнопочку Установить расширение. И это всё.

Исходный код расширения WIKI 2 регулярно проверяется специалистами Mozilla Foundation, Google и Apple. Вы также можете это сделать в любой момент.

4,5
Келли Слэйтон
Мои поздравления с отличным проектом... что за великолепная идея!
Александр Григорьевский
Я использую WIKI 2 каждый день
и почти забыл как выглядит оригинальная Википедия.
Статистика
На русском, статей
Улучшено за 24 ч.
Добавлено за 24 ч.
Альтернативы
Недавние
Show all languages
Что мы делаем. Каждая страница проходит через несколько сотен совершенствующих техник. Совершенно та же Википедия. Только лучше.
.
Лео
Ньютон
Яркие
Мягкие

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

Из Википедии — свободной энциклопедии

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

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

  • корень дерева — дробь ;
  • вершина с дробью имеет двух потомков: (левый) и (правый).

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

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

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

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

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

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

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

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

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

где и обозначают соответственно целую и дробную части числа .

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

Функция fusc

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

;
;
.

Последовательность значений совпадает с последовательностью числителей дробей в последовательности Калкина — Уилфа, то есть последовательностью

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

Таким образом (поскольку знаменатель каждой дроби в последовательности Калкина — Уилфа равен числителю следующей), -й член последовательности Калкина — Уилфа равен , а соответствие

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

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

  • Значение равно количеству гипердвоичных (англ. hyperbinary) представлений числа , то есть представлений в виде суммы неотрицательных степеней двойки, где каждая степень встречается не более двух раз[6]. Например, число 6 представляется тремя такими способами:
6 = 4 + 2 = 4 + 1 + 1 = 2 + 2 + 1 + 1, поэтому .

В оригинальной статье Калкина и Уилфа функция не упоминается, но рассматривается целочисленная функция , определённая для , равная количеству гипердвоичных представлений числа , и доказывается, что соответствие

является взаимно однозначным соответствием между множеством неотрицательных целых чисел и множеством рациональных чисел. Таким образом, для имеют место соотношения

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

«Гармония мира» И. Кеплера (1619), книга III (фрагмент)
«Гармония мира» И. Кеплера (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, поэтому .
  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. В этой статье определяется функция , которая оказывается связанной с функцией fusc соотношением .

Литература

Эта страница в последний раз была отредактирована 24 мая 2021 в 19:49.
Как только страница обновилась в Википедии она обновляется в Вики 2.
Обычно почти сразу, изредка в течении часа.
Основа этой страницы находится в Википедии. Текст доступен по лицензии CC BY-SA 3.0 Unported License. Нетекстовые медиаданные доступны под собственными лицензиями. Wikipedia® — зарегистрированный товарный знак организации Wikimedia Foundation, Inc. WIKI 2 является независимой компанией и не аффилирована с Фондом Викимедиа (Wikimedia Foundation).