Take the 2-minute tour ×
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.

I've got the following problem: The difinition of the funtion: Q(S,M). The purpose is to find the max number of possibilities how to write the funcition.

M is the max number, Smeans the sum of the numbers. To explain how it works, I'd like to show an example. Lets fill in Q(6,3). the result would be 7. I'll show:

1: 1-1-1-1-1-1
2: 2-1-1-1-1
3: 2-2-1-1
4: 2-2-2
5: 3-1-1-1
6: 3-2-1
7: 3-3

Max number was 3, so this are all posibilities to write a sum of 6.

I've tried several ways of writing down the posibilities, but I'm really stuck. has anyone seen this problem before? Which direction should I look?

NOTE: I'm not asking for the function of Q(,), do not (unless you really want) give this. I'm just looking for the right direction to look in.

Finally I wrote this: This works! thanks for helping.

private static int Q(int S, int M)
{
    if (S <= 0 || M == 1)
    {
        if (S < 0) return 0;
        return 1;
    }
    else
    {
        return Q(S, M - 1) + Q(S - M, M);
    }
}
share|improve this question
2  
Assuming this is a programming homework, you can use dynamic programming and recursion : note that $S(S,M) = k + S(S,M-k)$ looping all the k from $1$ to $S$ . I can give you a complete algorithm for an answer, but you said you don't want it :) –  kaharas Mar 14 '13 at 17:49
    
@kaharas thanks this is going to help me :) –  2pietjuh2 Mar 14 '13 at 18:11
    
If i look at your answer, and enter numbers I get the following: S(S,M) = consant = 6. this would mean 6=K + 6, but we are looping through k from 1-S so that means what you say is incorrect. If S(S,M) should have been Q(S,M) it would already make more sense. But also this does not give correct answers. I'll update my question according what I did. –  2pietjuh2 Mar 15 '13 at 11:14
add comment

1 Answer

You are looking at the partition function $q$: $q(n,k)$ is the number of partitions of $n$ into parts of sizes less than or equal to $k$. It satisfies a rather nice recurrence, but it has no nice closed form.

share|improve this answer
    
I've updated my question. I tried to implement this, but did not work. Could you please take a look again? –  2pietjuh2 Mar 15 '13 at 11:28
add comment

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.