How many combinations of Sums?

[schielrn]

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]

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]

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]

I think you mean 2^9-1 = 511

Unless you're checking the null set...

 

[schielrn]

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