Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm looking for material to study the following problem,

Suppose I have $N$ numbers, and I know that the sum of $M$ of those number equals $k$. The goal is to find all combinations of cardinality (is cardinality an appropriate word here?) $M$ that when summed equal $k$.

In addition: All $N$ values are positive.

share|improve this question
    
It's the "subset sum" problem (or something very like it). –  Gerry Myerson May 4 '12 at 12:58
2  
It is related to the subset sum problem in which the problem is to find one subset which sums to a given integer. Instead, you want to find all such subsets of a given size. –  Chris Taylor May 4 '12 at 13:01
    
    
If the number are only $\geq 0$, there is a dynamic programming solution O(k*M) (for find the number of them, for enumerating them it's O(k*M) + O(number of possible set) ). In general the problem is not tractable, so you need to check if there are additional costraint in your problem. –  carlop May 4 '12 at 13:34

1 Answer 1

The answer is: $\binom{k+N-1}{k}$(binomial coefficient). Or $\binom{M+N-1}{M}$, since M=k by your definition.

You questions is equivalent to the question: How many possibilites are there to distribute k indistinquishable balls into N pots?

Here is the argumentation:

g= the number of possiblilities to distribute N balls to M pots, when the pots are not restriced in the number of balls they can hold.

= number of possibilities to distribute M-1 walls and N balls with in a long que of balls and walls (see illustration). (If the row starts with a wall, that means the first pot was empty.)

= number of possibilities to distribute the N balls to N+M-1 pots, which can hold one ball on maximum. (The previous walls are now represented by the empty pots.)

The last problem is the well-known case that is answered by the binomial coefficient. (n+M-1 above n).

It might be a bit tough to follow the idea (and to understand my english), but maybe this picture will help you: https://imgur.com/j2dUC

share|improve this answer
    
My apologies for being unclear, $M$ is the number of elements which sum to $k$. –  csta May 4 '12 at 13:52
    
Oh, I think it's only now that I understand your question. –  Konstantin May 4 '12 at 13:54

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.