On the number of hypercubic bipartitions of an integer

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