Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Suppose you have a partition p of n into atmost k parts, say $$\{i_1, i_2, ..., i_j, ..., i_{k-1}\}$$ For example $\{1, 4\}$ is a partition of 10 into 3 parts (in this notation i am specifying the partition points, not the part lengths, i.e {1} , {2,3,4}, {5,6,7,8,9,10} are the three partitions)

Consider $$I(n, k) = min_p \sum_j {\frac {(i_{j+1} - i_j)} {2^{j}}}$$

Can we say anything meaningful about a lower bound on $I(n, k)$? I am specifically interested in the question when k is a function of n that grows slowly, like $log \ n$, or slower than $n^{1/{\epsilon}}$ for any ${\epsilon} > 0$.

I'm actually not sure if anything meaningful can be said here, so any ideas on how to approach this question would be very welcome

Any pointers to literature in this regard or a counter example showing no meaningful bound exists will be great. Intuitively, it seems like if i pick a partition of size $log \ n$ for example, no matter how i choose such a partition I cannot have $I(n, k) = O(1)$ for example. So I would probably guess $I(n,O(log\ n)) = O(log \ n)$.

share|improve this question
    
It seems your question is not about partitions of integers but just about sequences $1\le i_1\lt\cdots\lt i_{k-1}\lt n$. For given $k$, the minimum occurs when the sequence is $1,2,\ldots,k{-}1$. But one of us must be missing something. –  Brendan McKay Apr 22 at 5:13
    
I think the problem statement was confusing. Your solution is right as stated. –  Ram Apr 22 at 7:11

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.