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

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

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

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

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

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

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

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

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

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

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

${\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}},\quad i=1,2,\dots ,$

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

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

Функція fusc

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

$b(2n+1)=b(n),$

$b(2n+2)=b(n)+b(n+1).$

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

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

Див. також

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

Література

• Calkin, N., Wilf H. S. Recounting the Rationals // The American Mathematical Monthly. — 2000. — Т. 107, № 4 (12 листопада). — С. 360—363. Архівовано з джерела 3 вересня 2021. Процитовано 15 серпня 2021. (JSTOR 2589182 [Архівовано 15 серпня 2021 у Wayback Machine.])
• Айгнер М., Циглер Г. Доказательства из Книги. Лучшие доказательства со времён Евклида до наших дней (пер. с англ.). — М. : Мир, 2006. — С. 105—109. — ISBN 5-03-003690-3.
• Dijkstra, E. W. Selected Writings on Computing: A Personal Perspective. — Springer-Verlag, 1982. — ISBN 0-387-90652-5. (Див. документи EWD 570 [Архівовано 15 серпня 2021 у Wayback Machine.] і EWD 578 [Архівовано 15 серпня 2021 у Wayback Machine.], відтворені в цій книзі.)
• Stern M. Über eine zahlentheoretische Funktion // Journal für die reine und angewandte Mathematik. — 1858. — Т. 55 (12 листопада). — С. 193—220.
• Щетников А. И. Алгоритм разворачивания всех числовых отношений из отношения равенства и идеальные числа Платона // ΣΧΟΛΗ. — 2008. — Т. 2 (12 листопада). — С. 55—74. — ISSN 1995-4328. Архівовано з джерела 5 лютого 2020. Процитовано 15 серпня 2021.