In how many ways can N be written as a sum of positive numbers less or equal to K? 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.
 A: 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.
