SOLUTION: Given a set of N numbers, find the number of distinct possible sums that can be obtained by taking any number of elements from the N number of numbers and adding them. this is a

Algebra.Com
Question 892316: Given a set of N numbers, find the number of distinct possible sums that can be obtained by taking any number of elements from the N number of numbers and adding them.
this is a generalised question need to derive a general formula

Answer by Edwin McCravy(20054)   (Show Source): You can put this solution on YOUR website!
Taking N=5, it's quite easy to see that every sum of {1,10,100,1000,10000} 
would be unique.

On the other hand, also for N=5, it's quite easy to see that the sums of
{2,4,6,8,10} would not all be unique.

So there is no such general formula.  That's because for there to be a general
formula, the number of distinct sums would have to be the same for all sets of 5
distinct numbers.  And as we see that is not the case. 

To esplain further with smaller set:

Suppose you are given the set of N = 3 numbers {1,2,3}.
Let's form all distinct sums by taking any number of
numbers and adding them:

1 = 1
2 = 2
3 = 3
1+2 = 3
1+3 = 4
2+3 = 5
1+2+3 = 6

The 3 appears as a sum twice, so there are 6 distinct sums.

Now suppose you are given the set of N = 3 numbers {1,2,4}.
Let's form all possible sums by taking any number of
numbers and adding them:

1 = 1
2 = 2
4 = 4
1+2 = 3
1+4 = 5
2+4 = 6
1+2+4 = 7

None of those sums appear twice, so there are 7 distinct sums.

No general formula can could give you both 6 and 7 when you 
substitute N=3 into it.

So there can be no such general formula.  It would depend on
how many different ways you could get the same sum by adding 
different combinations of the numbers.

Sorry.

Edwin

RELATED QUESTIONS

Let S be a set of distinct integers. What is the smallest number of elements that S must (answered by CPhill,greenestamps,ikleyn)
is set A has 3 elements and set B has 4 elements: a. what is the greatest number of... (answered by stanbon)
Given that set A has 15 elements& set B has 15 ,what is the maximum & minimum possible... (answered by srinivas.g)
given that number of subset of a set A is 16. find the number of elements in... (answered by Fombitz)
sample n=5 elements from a total of N=50 elements. what is the number of different... (answered by stanbon)
Calculate the number of license plates that can be formed by using three distinct letters (answered by rfer)
Find the number n of distinct permutations that can be formed from all the letters of :... (answered by math_helper)
Find the number n of distinct permutations that can be formed from all the letters of... (answered by ikleyn)
A set contains five integers. when distinct elements of this set are added togehter, two... (answered by 303795)