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

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

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

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

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

Властивості дерева Калкіна — Вілфа

Основні властивості

• Всі дроби, розташовані у вершинах дерева, нескоротні;
• Будь-який нескортний раціональний дріб зустрічається в дереві рівно один раз.

Послідовність Калкіна — Вілфа

Обхід у ширину дерева Калкіна — Вілфа (шлях обходу показано рожевою спіраллю)

З наведених вище властивостей випливає, що послідовність додатних раціональних чисел, одержувана внаслідок обходу «в ширину»^[3] (англ. breadth-first traversal) дерева Калкіна — Вілфа (звана також послідовністю Калкіна — Вілфа; див. ілюстрацію),

${\displaystyle {\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 }$

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

Цю послідовність можна задати рекурентним співвідношенням^[4]

${\displaystyle q_{1}=1;}$

${\displaystyle 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 ,}$

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

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

Функція fusc

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

${\displaystyle \operatorname {fusc} (1)=1}$;

${\displaystyle \operatorname {fusc} (2n)=\operatorname {fusc} (n)}$;

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

Послідовність значень ${\displaystyle \operatorname {fusc} (n),n=1,2,3,\dots }$ збігається з послідовністю чисельників дробів у послідовності Калкіна — Вілфа, тобто послідовністю

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

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

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

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

Функцію ${\displaystyle \operatorname {fusc} }$ може бути, крім зазначених вище рекурентних співвідношень, визначити так.

• Значення ${\displaystyle \operatorname {fusc} (n+1),n\geqslant 0}$ дорівнює кількості гіпердвійкових (англ. hyperbinary) подань числа ${\displaystyle n}$, тобто подань у вигляді суми невід'ємних степенів двійки, де кожен степінь ${\displaystyle 2^{k}}$ зустрічається не більше двох разів^[6]. Наприклад, число 6 подається трьома такими способами:

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

• Значення ${\displaystyle \operatorname {fusc} (n+1),n\geqslant 0}$ дорівнює числу всіх непарних біноміальних коефіцієнтів вигляду ${\displaystyle {\binom {n-r}{r}}}$, де ${\displaystyle 0\leqslant 2r<n}$^[7].

В оригінальній статті Калкіна і Вілфа функція ${\displaystyle \operatorname {fusc} }$ не згадується, але розглядається цілочисельна функція ${\displaystyle b(n)}$, визначена для ${\displaystyle n=0,1,2,\dots }$, що дорівнює кількості гіпердвійкових подань числа ${\displaystyle n}$, і доводиться, що відповідність

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

є взаємно однозначною відповідністю між множиною невід'ємних цілих чисел і множиною раціональних чисел. Таким чином, для ${\displaystyle n=0,1,2,\dots }$ мають місце співвідношення

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

${\displaystyle b(2n+1)=b(n),}$

${\displaystyle b(2n+2)=b(n)+b(n+1).}$

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

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

Див. також

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