Дерево Калкіна — Вілфа

Дерево Калкіна — Вілфа

Дерево Калкіна — Вілфа (Шаблон:Lang-en) — орієнтоване двійкове дерево, у вершинах якого розташовані додатні раціональні дроби за таким правилом:

• корінь дерева — дріб $\frac{1}{1}$;
• вершина з дробом $\frac{m}{n}$ має двох нащадків: $\frac{m}{m+n}$ (лівий) і $\frac{m+n}{n}$ (правий).

Дерево описали Нейл Калкін і Шаблон:Не перекладено (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 Шаблон:Webarchive)
• Шаблон:Книга
• Шаблон:Книга (Див. документи EWD 570 Шаблон:Webarchive і EWD 578 Шаблон:Webarchive, відтворені в цій книзі.)
• Шаблон:Стаття
• Шаблон:Стаття