How Can I Find All Sum Combinations?

Question

What's the easiest way to calculate all combinations of numbers, in sets of 5, that eqaul n. For instance, say n=20. Sum combinations would include:
20+0+0+0+0
19+1+0+0+0
....
5+5+5+5+0
....etc

Is there a mathmatical formula that would lead me to those sums without going through all combinations individually? I'm not a math whiz, so details will be GREATLY appreciated.

Please let me know if you have any further questions!

Thanks!
--Dan

I will be writing a program - I just want to know the math to write the program most efficiently.

Answer 1

What you're talking about is called a 'composition' of n into k parts such that n = a_1+a_2+.....a_k and there is an algorithm for it in 'Combinatorial Algorithms', by Nijenhuis and Wilf (Academic Press, 1975) ISBN 0-12-519250-9 Ch.5.

It's almost certainly out of print, so you'll have to find a copy in the math section of a University Library, or have your local Librarian get it for you on a loan.

Unfortunately, there is no 'easy' way to get all of the partitions of n into k parts except going through and writing them all down. There **is** an expression for how many of them there will be and it's given by
(n+k-1)!/(n!(k-1)!)
Where ! means 'factorial' and is calculated as n*(n-1)*(n-2)....3*2*1 = n!

So, for example, the are 10626 ways to compose 20 with 5 digits.


Doug

Answer 2

20+0+0+0+0

Answer 3

Your question doesn't specify, but I assume you are requiring all the numbers in the sets to be non-negative.

I've thought about this problem a bit, and I don't think there's an easy mathematical formula for this type of problem. That said I think you could in optimize the program somewhat with a mathematical understanding of the problem.

For small values of n, such as n = 20, just writing a "brute force" computer program would probably give the quickest results. I'm thinking I could write a macro in Excel VBA in about 20 minutes to solve this problem.

Note, I'm not suggesting Excel VBA as the optimal environment, but I often times use Excel VBA for doing quick solutions like this because it's a programming environment that's easy to come by - I can borrow a public lab computer or a friend's laptop and write a quick program to answer a question.


EDIT: Based upon doug_donaghue's answer, I did some searching on the net and found a nice page on "Composition". Based upon the Wikipedia page, it appears you are looking for a "weak composition". The formula on the Wikipedia page appears to be for a non-weak composition - I get 3876 compositions when I used it.

Answer 4

You could try nested for loops like this:

for x[1] = 0 to 20
for x[2] = 0 to (20-x[1])
for x[3] = 0 to (20-x[1] -x[2])
for x[4] = 0 to (20-x[1] -x[2] -x[3])
x[5] = 20-x[1] -x[2] -x[3] -x[4]