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.
تحميل البحث