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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.