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

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

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

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

Дерево описали і ^[en] (2000) у зв'язку із задачею явного перерахунку множини раціональних чисел.

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

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

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

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

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

З наведених вище властивостей випливає, що послідовність додатних раціональних чисел, одержувана внаслідок обходу «в ширину» (англ. 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 }$

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

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

${\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) такими рекурентними співвідношеннями:

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

В оригінальній статті Калкіна і Вілфа функція ${\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 (фрагмент)

Див. також

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

Примітки

1. Див. статтю Calkin, Wilf (2000) у списку літератури.
2. Тобто явного задання взаємно однозначної відповідності між множиною натуральних чисел і множиною (додатних) раціональних чисел. Стандартні доведення зліченності множини раціональних чисел зазвичай не використовують явного задання зазначеної відповідності.
3. У цьому випадку обхід «у ширину» відповідає послідовному обходу кожного рівня (починаючи від верхнього) дерева Калкіна — Вілфа зліва направо (див. першу ілюстрацію).
4. Знайшов Моше Ньюмен (Moshe Newman); див. книгу Айгнера і Ціглера в списку літератури, с. 108.
5. Документ EWD 570: An exercise for Dr. R. M. Burstall [ 15 серпня 2021 у Wayback Machine.]; відтворений у книзі Dijkstra (1982) (див. список літератури), с. 215—216.
6. При цьому вважають, що число 0 має єдине («порожнє») гіпердвійкове подання 0 = 0, тому ${\displaystyle \operatorname {fusc} (0+1)=1}$.
7. Див. Carlitz, L. A problem in partitions related to the Stirling numbers // Bulletin of the American Mathematical Society. — 1964. — Т. 70, № 2 (9 липня). — С. 275—278. з джерела 21 січня 2022. Процитовано 15 серпня 2021. В цій статті визначається функція ${\displaystyle \theta _{0}(n)}$, яка виявляється пов'язаною із функцією fusc співвідношенням ${\displaystyle \theta _{0}(n)=\operatorname {fusc} (n+1)}$.

Література

• Calkin, N., Wilf H. S. Recounting the Rationals // The American Mathematical Monthly. — 2000. — Т. 107, № 4 (9 липня). — С. 360—363. з джерела 3 вересня 2021. Процитовано 15 серпня 2021. (JSTOR 2589182 [ 15 серпня 2021 у Wayback Machine.])
• Айгнер М., Циглер Г. Доказательства из Книги. Лучшие доказательства со времён Евклида до наших дней (пер. с англ.). — М. : Мир, 2006. — С. 105—109. — .
• Dijkstra, E. W. Selected Writings on Computing: A Personal Perspective. — Springer-Verlag, 1982. — . (Див. документи 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 (9 липня). — С. 193—220.
• Щетников А. И. Алгоритм разворачивания всех числовых отношений из отношения равенства и идеальные числа Платона // . — 2008. — Т. 2 (9 липня). — С. 55—74. — ISSN 1995-4328. з джерела 5 лютого 2020. Процитовано 15 серпня 2021.