# How many are possibilities to build count $n$ summing $k$ other counts?

I have got an integer $n$. I have to build it by summing $k$, not necessary, different integers. Is there any overall formula to count how many are possibilities to build count $n$ summing $k$ other counts?

Every integers being summed have to be $\ge$ 0.

Example:

$n = 5$, $k=2$ : 1+4=5, 2+3=5, 5+0=5 --- score: 3

$n = 5$, $k=3$ : 1+1+3=5, 1+2+2=5, 1+4+0=5, 2+3+0=5, 5+0+0 --- score: 5

• What are the scores for (5,3), (5,4), (5,5), (5,6)?
– caub
Jun 14 '14 at 11:10
• @kwak just added Jun 14 '14 at 17:26
• you forgot 5+0+0
– caub
Jun 14 '14 at 20:48

This is called combinations of $n$.
Picture your integer $n$ as $n + k$ ones (so every summand is at least 1), separated by $k - 1$ plus signs, thus for $n = 5$ and $k = 3$ you are looking at, e.g. $$11+1+11111$$ This is $2 + 1 + 5$, that means $1 + 0 + 4$ by subtracting the extra $k$ ones we added to have all non-empty stretches of ones. As there are $\binom{n + k - 1}{k - 1}$ ways of distribuing the $k - 1$ plus signs among the $n + k - 1$ spaces between ones, your result follows.
This kind of argument is called stars and bars, by using $|$ and $*$ instead of ones and plus.
A fun way is to use generating functions. The generating function for $\mathbb{N}_0$ is just: $$N(z) = 1 + z + z^2 + \ldots = \frac{1}{1 - z}$$ The generating function for the ways of adding up $n$ by $k$ elements of $\mathbb{N}_0$ is then just: $$N^k(z) = \frac{1}{(1 - z)^k}$$ and the corresponding coefficient is nothing more than: $$[z^n] N^k(z) = (-1)^n \binom{-k}{n} = \binom{n + k - 1}{k - 1}$$