Author 
Message 
Guest

Posted: Wed Aug 17, 2005 10:02 am Post subject:
Sum of combinations



Hi,
I am looking for help  I would appreciate any help, tip or pointer to
the right direction... thanks.
The problem is as follows:
I have the set S={0,1,2... n1}
I am looking for sum of all the different combination of length k.
There are C(n,k) combinations of elements from the above set. For such
a combination, sum all its elements. I am looking for the sum of all
these combinations sums.
Alternatively, I am multiplying k elements like a^j, a is constant, and
j belongs to S. I am summing over all different combinations of
kproducts, such that the power sums up, as described above. I would
like to describe this with easier series I can analyse, or at least
estimate the leading powers.
Thanks,
Amit Miller
(UCL) 

Back to top 


Matthew Roozee science forum beginner
Joined: 22 Oct 2005
Posts: 7

Posted: Sat Oct 22, 2005 5:35 pm Post subject:
Re: Sum of combinations



If I understand your question correctly, you are saying "take all C(n,k)
subsets of S then sum all of the elements for each subset and, in turn,
sum those."
As an example, if S = {0,1,2,3} and k = 2 there are C(4,2) = 6 subsets
with 2 elements:
{0,1} > sum = 1
{0,2} > sum = 2
{0,3} > sum = 3
{1,2} > sum = 3
{1,3} > sum = 4
{2,3} > sum = 5
Grand Total = 1 + 2 + 3 + 3 + 4 + 5 = 18
I see two straightforward ways to resolve this.
The first is to observe that when k > 0, each element of S will appear
in exactly C(n1,k1) subsets. So summing them all together will give
us C(n1,k1) zeroes, ones, twos, etc. and our total is:
C(n1,k1)*n*(n1)/2 or in the example: C(3,1)*4*3/2 = 18.
The n(n1)/2 term comes from the sum of the integers 0,...,n1.
The second is to observe that there are C(n,k) subsets and the average
sum of these subsets is just k times the average of the set. The
average for S is just (n1)/2. Multiplying this by k gives our average
sum k(n1)/2 and then by C(n,k). In our example, this would give
2*3/2*C(4,2) = 18.
To see that these are really just the same solution, recall that C(a,b)
= a!/[(ab!)(b!)] and:
The first solution = C(n1,k1)*n*(n1)/2 =
= (n1)!/{[(n1)(k1)]!*(k1)!}*n*(n1)/2 :: expanding C(n1,k1)
= n*(n1)!/[(nk)!*(k1)!]*(n1)/2 :: moving the n and simplifying
= n!*k/[(nk)!*k*(k1)!]*(n1)/2 :: mult. and div. by k, combine n!
= n!/[(nk)!*k!]*k*(n1)/2 :: combine k! and move the other k
= C(n,k)*k*(n1)/2 = the second solution.
 Matt
milleramit@gmail.com wrote:
Quote:  Hi,
I am looking for help  I would appreciate any help, tip or pointer to
the right direction... thanks.
The problem is as follows:
I have the set S={0,1,2... n1}
I am looking for sum of all the different combination of length k.
There are C(n,k) combinations of elements from the above set. For such
a combination, sum all its elements. I am looking for the sum of all
these combinations sums.
Alternatively, I am multiplying k elements like a^j, a is constant, and
j belongs to S. I am summing over all different combinations of
kproducts, such that the power sums up, as described above. I would
like to describe this with easier series I can analyse, or at least
estimate the leading powers.
Thanks,
Amit Miller
(UCL)



Back to top 


Google


Back to top 



The time now is Sat Nov 25, 2017 1:47 am  All times are GMT

