Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
A suggestion: use ''num'' to abbreviate ''number''. Even better, don't use abbreviations... –  David Mitra Nov 9 '11 at 11:44
3  
Compositions sure are turning up a lot lately here in math.SE... –  J. M. Nov 9 '11 at 11:50
1  
Like, in here... –  J. M. Nov 9 '11 at 12:07
1  
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
1  
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

3 Answers 3

up vote 2 down vote accepted

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

share|improve this answer

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

share|improve this answer
    
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
1  
The usual word, as noted in the comments on the original question, is "composition". –  Gerry Myerson Nov 10 '11 at 6:06

Your 415 and your 13624.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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