In how many ways can N be written as a sum of positive numbers less or equal to K?

Question

I'm trying to solve an informatics problem, and I need to know if there is a formula that can be applied to solve the problem.

Any help appreciated!

Edit: This question was flagged as a possible duplicate of some other question. I want to clarify that the number of numbers added is arbitrary, though the numbers added must be less or equal to K.

Answer 1

This function will calculate the answer:

number_of_partitions(N, max):
    if      N = 0:   return 1
    else if N < 0:    return 0
    else:
        total ← 0
        for i in 1 … max do:
            total ← total + number_of_partitions(N-i, max)
        return total

For example, number_of_partitions(4,2) returns $5$, because it is counting

$$\begin{align} 4 &= 1+1+1+1\\ 4 &= 2 + 1 +1 \\ 4 &= 1 + 2 + 1 \\ 4 &= 1 + 1 + 2 \\ 4 &= 2 + 2 \end{align}$$

but not $$\begin{align}4 & = 3 +1 \\ 4& = 1+3\\4 & = 4.\end{align}$$

How does this work? The recursion is the important part. We are going to take the original number $N$ and split off parts one at a time. The part we split off can be any size $i$ from $1$ up to $max$. Then we count how many ways there are to partition the remainder $N-i$ and add up the results for each $i$.

The only subtle point is in the base case for the recursion. number_of_partitions(0, max) is always 1, because there is exactly one partition of $N=0$, namely the empty partition.

This counting considers $1+1+2$ to be distinct from $2+1+1$. If you want them to be the same, do the recursion with total ← total + number_of_partitions(N-i, i) instead, and it will only count the ways which are sorted largest-to-smallest.