Contents Online

# Journal of Combinatorics

## Volume 14 (2023)

### Number 3

### On Mallows’ variation of the Stern–Brocot tree

Pages: 339 – 368

DOI: https://dx.doi.org/10.4310/JOC.2023.v14.n3.a3

#### Author

#### Abstract

Mallows (2011) showed that if we, starting with the initial sequence $\langle \frac{0}{1}, \frac{1}{1} \rangle$, successively insert two fractions between two adjacent fractions in a certain way, then every fraction from $\mathbb{Q} \cap (0,1)$ eventually appears. In this article, we first show that Mallows’ variation $\mathrm{MT}_k (k \geq 0)$ of the Stern–Brocot tree can be obtained from the left subtree $\mathrm{SBT}^L$ of the Stern–Brocot tree. We then present algorithms for the following two questions: Where is the $j^\prime \textrm{th}$ element of $\mathrm{MT}_{k^\prime}$ placed in $\mathrm{SBT}^L$? Conversely, where is the $j \textrm{th}$ element of the $k \textrm{th}$ level of $\mathrm{SBT}^L$ placed in Mallows’ variation? We then do similar things for the tree $\mathrm{R}\textrm{-}\mathrm{DT}$ obtained from the Ducci tree by reversing the paths. More precisely, inspired by the way that we obtained Mallows’ variation from the left subtree of the Stern–Brocot tree, we introduce a variation $\mathrm{VT}_k (k \geq 0)$ of the tree $\mathrm{R}\textrm{-}\mathrm{DT}$ and study analogous questions concerning placement between $\mathrm{VT}_k (k \geq 0)$ and the left subtree $\mathrm{R}\textrm{-}\mathrm{DT}^L$ of the tree $\mathrm{R}\textrm{-}\mathrm{DT}$. We also provide an algorithm, which, given a $k \geq 2$, outputs the ordered set $\mathrm{VT}_k$ as a sequence.

Lastly, we explain how Mallows’ variation of the Stern–Brocot tree and our variation of the tree $\mathrm{R}\textrm{DT}$ are related to each other.

#### Keywords

Mallows’ variation of the Stern–Brocot tree, Stern–Brocot tree, Ducci tree, reversal of the paths, continued fraction

#### 2010 Mathematics Subject Classification

Primary 11B75. Secondary 11A55.

Received 17 November 2021

Published 28 December 2022