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

Дерево Калкіна — Вілфа (англ. 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}$.

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

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).}$

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

• Calkin, N., Wilf H. S. Recounting the Rationals // The American Mathematical Monthly. — 2000. — Т. 107, № 4 (27 липня). — С. 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 (27 липня). — С. 193—220.
• Щетников А. И. Алгоритм разворачивания всех числовых отношений из отношения равенства и идеальные числа Платона // ΣΧΟΛΗ. — 2008. — Т. 2 (27 липня). — С. 55—74. — ISSN 1995-4328. Архівовано з джерела 5 лютого 2020. Процитовано 15 серпня 2021.