Search   Memberlist   Usergroups
 Page 1 of 1 [2 Posts]
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... n-1}
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
k-products, 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)
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 straight-forward ways to resolve this.

The first is to observe that when k > 0, each element of S will appear
in exactly C(n-1,k-1) subsets. So summing them all together will give
us C(n-1,k-1) zeroes, ones, twos, etc. and our total is:
C(n-1,k-1)*n*(n-1)/2 or in the example: C(3,1)*4*3/2 = 18.
The n(n-1)/2 term comes from the sum of the integers 0,...,n-1.

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 (n-1)/2. Multiplying this by k gives our average
sum k(n-1)/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!/[(a-b!)(b!)] and:

The first solution = C(n-1,k-1)*n*(n-1)/2 =
= (n-1)!/{[(n-1)-(k-1)]!*(k-1)!}*n*(n-1)/2 :: expanding C(n-1,k-1)
= n*(n-1)!/[(n-k)!*(k-1)!]*(n-1)/2 :: moving the n and simplifying
= n!*k/[(n-k)!*k*(k-1)!]*(n-1)/2 :: mult. and div. by k, combine n!
= n!/[(n-k)!*k!]*k*(n-1)/2 :: combine k! and move the other k
= C(n,k)*k*(n-1)/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... n-1} 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 k-products, 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)

 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
 Page 1 of 1 [2 Posts]
 The time now is Sun Feb 17, 2019 1:26 pm | All times are GMT
 Jump to: Select a forum-------------------Forum index|___Science and Technology    |___Math    |   |___Research    |   |___num-analysis    |   |___Symbolic    |   |___Combinatorics    |   |___Probability    |   |   |___Prediction    |   |       |   |___Undergraduate    |   |___Recreational    |       |___Physics    |   |___Research    |   |___New Theories    |   |___Acoustics    |   |___Electromagnetics    |   |___Strings    |   |___Particle    |   |___Fusion    |   |___Relativity    |       |___Chem    |   |___Analytical    |   |___Electrochem    |   |   |___Battery    |   |       |   |___Coatings    |       |___Engineering        |___Control        |___Mechanics        |___Chemical

 Topic Author Forum Replies Last Post Similar Topics How many combinations possible? nowwicked@yahoo.com Math 5 Tue Jun 27, 2006 6:35 pm Combinations satisfying linear equations? BDH Math 11 Tue Jun 27, 2006 9:58 am Combinations and Investment Strategies Baker Probability 0 Sun Jun 18, 2006 7:19 pm How Many Combinations for THIS?? Dom Combinatorics 6 Fri May 05, 2006 10:10 pm Maple bugs are ubiquitous: "Maple is not recognizing gree... Vladimir Bondarenko Math 0 Sat Apr 22, 2006 8:10 am