On the number of hypercubic bipartitions of an integer

For n≤2^k$n\le 2^k$ we study the maximum number of edges of an induced subgraph on n$n$ vertices of the k$k$-dimensional hypercube _Qk$Q_k$. In the process we revisit a well-known divide-and-conquer maximin recurrence f(n)=max(min(_n1,_n2)+f(_n1)+f(_n2))$f\left(n\right)=max(min(n_1,n_2)+f\left(n_1\right)+f\left(n_2\right))$ where the maximum is taken over all proper bipartitions n=_n1+_n2$n=n_1+n_2$. We first use known results to present a characterization of those bipartitions n=_n1+_n2$n=n_1+n_2$ that yield the maximum f(n)=min(_n1,_n2)+f(_n1)+f(_n2)$f\left(n\right)=min(n_1,n_2)+f\left(n_1\right)+f\left(n_2\right)$. Then we use this characterization to present the main result of this article, namely, for a given n∈N$n\in \mathbb{N}$, the determination of the number h(n)$h\left(n\right)$ of these bipartitions that yield the said maximum f(n)$f\left(n\right)$. We present recursive formulae for h(n)$h\left(n\right)$, a generating function h(x)$h\left(x\right)$, and an explicit formula for h(n)$h\left(n\right)$ in terms of a special representation of n$n$.