In this paper we demonstrate connections between three seemingly unrelated concepts. (1) The discrete isoperimetric problem in the infinite binary tree with all the leaves at the same level, $ { \mathcal T}_{ \infty}$: The $n$-th edge isoperimetric number $\delta(n)$ is defined to be $\min_{ |S|=n, S \subset V({ \mathcal T}_{ \infty})} |(S,\bar{ S})|$, where $(S,\bar{ S})$ is the set of edges in the cut defined by $S$. (2) Signed almost binary partitions: This is the special case of the coin-changing problem where the coins are drawn from the set ${ \pm (2^d - 1): $d$ is a positive integer}$. The quantity of interest is $\tau(n)$, the minimum number of coins necessary to make change for $n$ cents. (3) Certain Meta-Fibonacci sequences: The Tanny sequence is defined by $T(n)=T(n{ -}1{ -}T(n{ -}1))+T(n{ -}2{ -}T(n{ -}2))$ and the Conolly sequence is defined by $C(n)=C(n{ -}C(n{ -}1))+C(n{ -}1{ -}C(n{ -}2))$, where the initial conditions are $T(1) = C(1) = T(2) = C(2) = 1$. These are well-known "meta-Fibonacci" sequences. The main result that ties these three together is the following: $$ \delta(n) = \tau(n) = n+ 2 + 2 \min_{ 1 \le k \le n} (C(k) - T(n-k) - k).$$ Apart from this, we prove several other results which bring out the interconnections between the above three concepts.
Categories: math.CO