FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups 
 ProfileProfile   PreferencesPreferences   Log in to check your private messagesLog in to check your private messages   Log inLog in 
Forum index » Science and Technology » Math » Combinatorics
Sum of combinations
Post new topic   Reply to topic Page 1 of 1 [2 Posts] View previous topic :: View next topic
Author Message
Guest






PostPosted: Wed Aug 17, 2005 10:02 am    Post subject: Sum of combinations Reply with 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)
Back to top
Matthew Roozee
science forum beginner


Joined: 22 Oct 2005
Posts: 7

PostPosted: Sat Oct 22, 2005 5:35 pm    Post subject: Re: Sum of combinations Reply with quote

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)
Back to top
Google

Back to top
Display posts from previous:   
Post new topic   Reply to topic Page 1 of 1 [2 Posts] View previous topic :: View next topic
The time now is Thu Oct 19, 2017 2:41 pm | All times are GMT
Forum index » Science and Technology » Math » Combinatorics
Jump to:  

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

Copyright © 2004-2005 DeniX Solutions SRL
Other DeniX Solutions sites: Electronics forum |  Medicine forum |  Unix/Linux blog |  Unix/Linux documentation |  Unix/Linux forums  |  send newsletters
 


Powered by phpBB © 2001, 2005 phpBB Group
[ Time: 0.0174s ][ Queries: 16 (0.0031s) ][ GZIP on - Debug on ]