Write a number N as a sum of K numbers

Question

I need to find the no of ways of partitioning a number N as a sum of K non-negative numbers.

Zeroes are also needed to be included in the sum.

Ordering does matter.

Example-

For $N=2,K=3 $

There are $6$ ways {1,1,0},{1,0,1},{0,1,1},{2,0,0},{0,0,2},{0,2,0}

I need an efficient recursive relation for this ?

Answer 1

Yes. Either the first number is zero, and you want $k-1$ numbers adding to $n$, or the first number is not zero. In the second case, find $k$ numbers that add to $n-1$, then add $1$ to the first number.

So $F(n,k)=F(n,k-1)+F(n-1,k)$
Use that to build up a bunch of values of $F(n,k)$ for, say $n=1..4$, $k=1..4$.

Answer 2

This is the bars and stars problem. Your problem is equivalent to this one:

How many ways are there to rearrange $N$ stars and $K-1$ bars? Answer: $\binom {N+K-1}{K-1}$

Think in the stars as balls that you have to put in a row of boxes, and think in the bars as the walls between boxes.