Дерево Калкіна — Вілфа () — орієнтоване двійкове дерево, у вершинах якого розташовані додатні раціональні дроби за таким правилом:
корінь дерева — дріб ; вершина з дробом має двох нащадків: (лівий) і (правий).
Дерево описали Нейл Калкін і (2000Див. статтю Calkin, Wilf (2000) у списку літератури.) у зв'язку із задачею явного перерахункуТобто явного задання взаємно однозначної відповідності між множиною натуральних чисел і множиною (додатних) раціональних чисел. Стандартні доведення зліченності множини раціональних чисел зазвичай не використовують явного задання зазначеної відповідності. множини раціональних чисел.
Властивості дерева Калкіна — Вілфа
Основні властивості
Всі дроби, розташовані у вершинах дерева, нескоротні; Будь-який нескортний раціональний дріб зустрічається в дереві рівно один раз.
Послідовність Калкіна — Вілфа
З наведених вище властивостей випливає, що послідовність додатних раціональних чисел, одержувана внаслідок обходу «в ширину»У цьому випадку обхід «у ширину» відповідає послідовному обходу кожного рівня (починаючи від верхнього) дерева Калкіна — Вілфа зліва направо (див. першу ілюстрацію). () дерева Калкіна — Вілфа (звана також послідовністю Калкіна — Вілфа; див. ілюстрацію),
визначає взаємно однозначну відповідність між множиною натуральних чисел і множиною додатних раціональних чисел.
Цю послідовність можна задати рекурентним співвідношеннямЗнайшов Моше Ньюмен (Moshe Newman); див. книгу Айгнера і Ціглера в списку літератури, с. 108.
де і позначають відповідно цілу і дробову частини числа .
У послідовності Калкіна — Вілфа знаменник кожного дробу дорівнює чисельнику наступного.
Функція fusc 1976 року Е. Дейкстра визначив на множині натуральних чисел цілочислову функцію fusc(n) такими рекурентними співвідношеннямиДокумент EWD 570: An exercise for Dr. R. M. Burstall ; відтворений у книзі Dijkstra (1982) (див. список літератури), с. 215—216.:
.
Послідовність значень збігається з послідовністю чисельників дробів у послідовності Калкіна — Вілфа, тобто послідовністю
1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, …
Таким чином (оскільки знаменник кожного дробу в послідовності Калкіна — Вілфа дорівнює чисельнику наступного), -й член послідовності Калкіна — Вілфа дорівнює , а відповідність
є взаємно однозначною відповідністю між множиною натуральних чисел і множиною додатних раціональних чисел.
Функцію може бути, крім зазначених вище рекурентних співвідношень, визначити так.
Значення дорівнює кількості гіпердвійкових () подань числа , тобто подань у вигляді суми невід'ємних степенів двійки, де кожен степінь зустрічається не більше двох разівПри цьому вважають, що число 0 має єдине («порожнє») гіпердвійкове подання 0 = 0, тому .. Наприклад, число 6 подається трьома такими способами:
6 = 4 + 2 = 4 + 1 + 1 = 2 + 2 + 1 + 1, тому .
Значення дорівнює числу всіх непарних біноміальних коефіцієнтів вигляду , де Див. В цій статті визначається функція , яка виявляється пов'язаною із функцією fusc співвідношенням ..
В оригінальній статті Калкіна і Вілфа функція не згадується, але розглядається цілочисельна функція , визначена для , що дорівнює кількості гіпердвійкових подань числа , і доводиться, що відповідність
є взаємно однозначною відповідністю між множиною невід'ємних цілих чисел і множиною раціональних чисел. Таким чином, для мають місце співвідношення
Дерево Кеплера і Saltus Gerberti
Див. також Дерево Штерна — Броко
Примітки
Література (JSTOR 2589182 )
(Див. документи EWD 570 і EWD 578 , відтворені в цій книзі.)