0
$\begingroup$

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

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

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.

$\endgroup$
1
  • $\begingroup$ I am sorry, but I do not understand fully your answer. For n=5 and k=2 binomial coefficient (5+2-1),(2-1) equals 30 - "wolframalpha.com/input/?i=%285%2B2-1%29!%2F%28%282-1%29!*%285-1%29!%29" Wolfram Alpha, not 3 as should be in my example. Can you explain me that more? $\endgroup$
    – TN888
    Jun 14 '14 at 15:09
1
$\begingroup$

If the order of summands doesn't matter, so you count 4+1 as equivalent to 1+4, then you need to count 'partitions of n into 2 parts'. This has no closed form formula, but it does have a nice recursion algorithm. See http://en.wikipedia.org/wiki/Partition_(number_theory)#Restricted_part_size_or_number_of_parts.

$\endgroup$
0
$\begingroup$

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} $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.