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

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

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 =?$

-
A suggestion: use ''num'' to abbreviate ''number''. Even better, don't use abbreviations... –  David Mitra Nov 9 '11 at 11:44
Compositions sure are turning up a lot lately here in math.SE... –  Ｊ. Ｍ. Nov 9 '11 at 11:50
Like, in here... –  Ｊ. Ｍ. Nov 9 '11 at 12:07
1. That's probably Frobenius. 2. What theorem? You've written down an equation full of undefined symbols - that's not a theorem. 3. I suppose you are interested in all solutions of that equation where $N$ is your sum, $n$ is arbitrary, $x_i$ come from your given numbers, and the $a_i$ are all 1. E.g., in your 2nd case, $N=13$; $x_i$ take values from 1, 2, 8; $a_i$ are all 1; and $n$ takes all values from 4 to 13. –  Gerry Myerson Nov 10 '11 at 6:11
P.S.: You asked how to get 415, and I told you in my answer. Did you not find that helpful? –  Gerry Myerson Nov 10 '11 at 6:12

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

-

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|)$.

-
Right answer, wrong question. I don't think this gives 415 for OP's 2nd example. OP seems to be counting $8+2+2+1$, $2+1+2+8$, $1+2+8+2$, etc., etc., as different. –  Gerry Myerson Nov 10 '11 at 0:00
So, I think it should be a permutation rather than combination as it counts order of combination too. –  Angelin Nadar Nov 10 '11 at 4:06
The usual word, as noted in the comments on the original question, is "composition". –  Gerry Myerson Nov 10 '11 at 6:06
-
It was useful & Iam finding how to get the series expansion? –  Angelin Nadar Nov 10 '11 at 7:39
Do you know how to compute the series ? –  Angelin Nadar Nov 10 '11 at 10:27
@Angelin If you don't have a computer, the best way to solve such problems is outlined in Gerry's answer. There is no easy way to compute the series. –  Byron Schmuland Nov 10 '11 at 14:42
Its not about easy way but to automate it. –  Angelin Nadar Nov 10 '11 at 16:49