Sign up ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let me put this into an example.

We have an array of the first $r$ (example $r=7$) natural numbers;

$1, 2, 3, 4, 5, 6, 7$

and given $k=3$, so you get to select any three integers from the pool above. Taken $1$, $6$ and $7$, we have their sum $14$. We get to partition this number ($14$) such that its $k$ parts all appear in the array above, like $14=2+5+7=3+4+7$ and so on

In this manner, which $k$ numbers' sum do you think can be partitioned into the most number of $k$ integers, in which any part can be at most $r$ from that array? Let me guess, this should be the sum of the last $k$ integers in the pool, right?

BTW I've used the terms pool and array, and integer and natural number in their same contexts. Sorry for that.


Yes, I guess it involves partitioning of the numbers' sum into distinct $k$ parts of which the largest part $r$ is the largest number in the array. Therefore, reinstating my previous example, we have $Q(14, 3:7)$ where 7 is the largest number in the array, consequently no part among the $k(=3)$ parts can exceed the number 7.

By the way, I remember having seen an asymptotic formula for $Q(n, k:r)$. I don't remember where that was. I'll let everyone know as soon as I find out.

To put this question in another way, which $k$ numbers' sum from the array (of the first $r$ natural numbers, in ascending order) will have the greatest number of $k$ distinct partitions with each part equal to or lesser than $r$?

share|cite|improve this question
You didn't state whether the integers need to be different, but it seems that you're assuming they are. In that case: No, certainly not the last $k$; in fact their sum is unique since every other sum is necessarily smaller. If the integers need not be different, then the most central sum (in this case $4+4+4=12$) would have the most representations, and I strongly suspect that this is also the case if they have to be different. – joriki Mar 13 '12 at 17:26
Remember the example of tossing two dice (so $k=2$). It is a familiar fact that the sum of $7$ occurs in the largest number of ways. – André Nicolas Mar 13 '12 at 18:37
@joriki: Yes, that's right. As a matter of fact,what I've posted above is (I guess) an expansion of your post. So, can it be the first $k$ integers (probably not)? Or the $k$ integers in the middle? – Mach9 Mar 14 '12 at 3:33
@André Nicolas: I don't understand what you're getting at. – Mach9 Mar 14 '12 at 3:33
@Mach9: Please edit the question accordingly. People shouldn't have to burrow to the end of the comments in order to understand the question. – joriki Mar 14 '12 at 10:01

Your Answer


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

Browse other questions tagged or ask your own question.