How to get number of combinations from given set of numbers to result a given sum?

Question

Eg:

sum = 10
Num of given nos: 1
Given nos: 1
Num of Combination: 1

sum = 13
Num of given nos: 3
Given nos: 1, 2, 8
Num of Combination: 415

sum = 15
Num of given nos: 5
Given nos: 1, 2, 3, 4, 5
Num of Combination: 13624

Case 1 explain: Only one combination is possible: $$1+1+1+1+1+1+1+1+1+1$$

I want to know how to get $415$ combinations for case $2$ as well as for case $3$.

Addition:

I came to know this has to be solved by Frobenius theorem $$N = \sum_{i=1}^n a_i \times x_i $$

but here what will $N,a_i, x_i =?$

Answer 1

Here's how you get 415 for Case 2. I'll leave case 3 (and the general case) to you.

Not counting order, there are 10 ways to make up 13 using 1s, 2s, and 8s:

$8+2+2+1$
$8+2+1+1+1$
$8+1+\cdots+1$
six 2s and one 1
five 2s and three 1s
four 2s and five 1s
three 2s and seven 1s
two 2s and nine 1s
one 2 and eleven 1s
thirteen 1s.

But order (evidently) counts. So, how many ways can you order 8, 2, 2, 1? You could order 4 distinct numbers 24 ways, but the 2s are indistinguishable, so we get 12.

How many ways to order 8, 2, 1, 1, 1? The 8 can go in any of 5 locations, the 2, in any of the reamaining 4 locations, so, 20.

For one 8 and five 1s, there are 6 places to put the 8, so, 6.

For the 2s and 1s, if there are $m$ 2s and $n$ 1s, then there are $(m+n)$-choose-$m$ orderings.

Putting it all together you get $$12+20+6+7+56+126+120+55+12+1=415$$

Answer 2

This can be solved with dynamic programming:

Denote the set of given numbers as $S$ and the number of required combinations for some number $n$ as $f(n)$. Then the following recurrent equation holds:

$$f(n)=\left\{ \begin{array}{ll} \sum\limits_{k \in S }f(n-k) & \textrm{if }n\not\in S, n > 0\\ \sum\limits_{k \in S }f(n-k) + 1 & \textrm{if }n\in S \\ 0 &\textrm{if } n < 0 \end{array}\right.$$

The main formula is given in line 1, the recurrence base - in line 2, and the impossible cases are cut out in line 3.

Thus $f(n)$ can be calculated in $O(n*|S|)$.

Answer 3

Your 415 and your 13624.