What is the pattern here? Q-function - SOLVED

Question

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

Answer 1

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.