# What is the pattern here? Q-function - SOLVED

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);
}
}

-
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

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.