Isoperimetric Sequences for Infinite Complete Binary Trees, Meta-Fibonacci Sequences and Signed Almost Binary Partitions

arXiv1210.0405MaRDI QIDQ6236049FDOQ6236049

Authors: L. Sunil Chandran, Anita Das, Frank Ruskey 

Publication date: 1 October 2012

Abstract: 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, ${mathcalT}_{infty}$: The $n$-th edge isoperimetric number $delta(n)$ is defined to be $$, where $$ 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 $$d$$. The quantity of interest is $au(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: ${\displaystyle }$ delta(n) = au(n) = n+ 2 + 2 min_{1 le k le n} (C(k) - T(n-k) - k).${\displaystyle }$ Apart from this, we prove several other results which bring out the interconnections between the above three concepts.

Mathematics Subject Classification ID

Trees (05C05)

This page was built for publication: Isoperimetric Sequences for Infinite Complete Binary Trees, Meta-Fibonacci Sequences and Signed Almost Binary Partitions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6236049)