# How many combinations of Sums?



## schielrn (Feb 4, 2008)

I'm working on something and I am trying to figure out how many combinations I should actually end up with?  Here is what I have:

If you have 1 & 2, you can have 3 different combinations for what I am working on:

1
1+2
2

If you have 1, 2 & 3, you can have 7 different combinations for what I am working on:
1
1+2
1+3
1+2+3
2
2+3
3

If you have 1, 2, 3 & 4, you can have 15 different combinations for what I am working on:
1
1+2
1+3
1+4
1+2+3
1+2+4
1+3+4
1+2+3+4
2
2+3
2+4
2+3+4
3
3+4
4

If you have 1, 2, 3, 4 & 5, you can have 30 different combinations for what I am working on:
1
1+2
1+3
1+4
1+5
1+2+3
1+2+4
1+2+5
1+3+4
1+3+5
1+4+5
1+2+3+4
1+2+3+5
1+3+4+5
1+2+3+4+5
2
2+3
2+4
2+5
2+3+4
2+3+5
2+4+5
2+3+4+5
3
3+4
3+5
3+4+5
4
4+5
5


Maybe I am missing some combinations, but I don't think I am.  I cannot for the life of me figure out a method to the growing number?  Usually I am good with this, but nothing is jumping out at me.  What I am trying to figure out is for 9 sum combinations?  Can anyone solve this or is it that I just have to list it out?

Hopefully someone can offer some advice on this?

Thanks,

Rob


----------



## Oaktree (Feb 4, 2008)

Think of it this way:

For a given subset, each number is either (a) included in the subset or (b) excluded from the subset.  So, for n numbers, there are 2^n possibilities.  Since you exclude the null subset where all of the numbers are excluded, you arrive at =2^n -1.

Also note that you forgot 1+2+4+5 in your count of 30.  Per the formula, the count should be 31.


----------



## schielrn (Feb 4, 2008)

Thanks for that.  I knew there was a way to solve for it, but I just kept drawing a blank.

Now I can run my macro and put in a counter to make sure I am checking all 512 combinations of 9 possible numbers.


----------



## Oaktree (Feb 4, 2008)

I think you mean 2^9-1 = 511 

Unless you're checking the null set...


----------



## schielrn (Feb 4, 2008)

Yes thank you.  I keep forgetting that, but my macro at the moment is only testing 165, so that helps me a lot.  Thank you again.  Here is a link to the topic where I am trying to help someone, but I need to scrap what I have a lay out an actual plan of attack.

http://www.mrexcel.com/forum/showthread.php?t=301311


----------

