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 was thinking a problem of finding the number of way to add M numbers, ranged 0 to K, to a give a desired sum. Doing some researches online, I find a way to use polynomial to achieve the goal. For example, suppose there are M numbers, each one ranged from 0 to K inclusive, if we consider the polynomial

$$(x^0 + x^1 + x^2 + \cdots + x^K)^M$$

the way to add those M numbers to get N is the coefficient of the term $x^N$, I also written a code to testify it. In this case, each number ranged 0 to K so there is duplicated numbers.

But I would like to extend the problem to the case with no duplicate numbers. I constrain that there are N different numbers $1, 2, \cdots, N$, pick M out of them ($M<N$) at a time, so all possible sums are

$$(1+2+\cdots+M), [2+\cdots+M+(M+1)], \cdots , [N+(N-1)+\cdots+(N-M+1)] $$

My question is how to figure out that how many way could that be from all possible M out of N numbers add up to above sum? I write a program to test that, when N, M are small (e.g. N=50, M=12), it is not that bad to enumerate all the cases, but if we increase N says to 100 or more, there are too many cases to retrieve. Any way like the polynomial method to do the trick quick?

I would like to add an example to clarify my questions. Let's say I have N=10 numbers, {1,2,3,4,5,6,7,8,9,10}, picking M=5 numbers out of them at a times (no duplicates), how many way I could pick 5 numbers out of those 10-number set such that the sum is 22?

share|improve this question
    
You mean how to choose $M$ terms in a set of $N$ numbers? –  JoeyBF Jun 16 at 14:19
    
I mean how to choose M terms in a set of N numbers so those M terms sum up to a given number –  user1285419 Jun 16 at 14:26

2 Answers 2

up vote 2 down vote accepted

The number of ways to select $M$ distinct values from $1,2,\dots, N$ with sum $S$ is the coefficient of $y^{M} x^S$ in the product $\prod_{j=1}^N (1+y \, x^j)$.

share|improve this answer
    
That's so beautiful. Thanks Byron. –  user1285419 Jun 16 at 16:16

I will do the case when $N$ is a multiple of $k$. The other is similar.

that is the same as $\frac{(1-x^k)^m}{(1-x)^m}$ which is simpler to compute as the product of two sums.

$(1-x^k)^m=\sum_{j=0}^m\binom{m}{j}(-1)^jx^{kj}$.

Note only the first $\lfloor\dfrac{N}{k}\rfloor$ terms can contribute to coefficient $N$.

$(1-x)^{-m}=\sum_{k=0}^{\infty} \binom{-m}{k}(-1)^j x^{j}$. Observe we only need terms of degree $kj$ in the second series. Cross multiplying the terms which contribute to $x^N$ you have your answer.

share|improve this answer
    
does this assure that all m numbers are unique? –  user1285419 Jun 16 at 14:27
    
This is just a simpler way to calculate the coefficient of $x^N$, it does this by calculating the coefficients of $(1-x^k)^m$ and the coefficients of $(1-x)^{-m}$ and cross multiplying those which give the desirable exponent $x^n$. –  Jorge Fernández Jun 16 at 14:30
    
Thanks Bananarama. I am still confusing on the math. I add an example to clarify my question and wonder if your reply is the solution for my question. Sorry if my words is misleading ;) –  user1285419 Jun 16 at 15:03
    
yup, this is exactly the problem I am answering :) Here is a similar question math.stackexchange.com/questions/620640/… –  Jorge Fernández Jun 16 at 15:11
    
um ... maybe I misunderstood the math ... but following your math or the reply found in the thread you gave. I didn't get the correct answer. For example, consider that I have a set of 10 numbers {1,2,3,4,5,6,7,8,9,10}, pick 2 unique numbers at a time, how many way I could pick the two numbers so they add up to 8? With simulation or simple enumeration,the possible solution is {1,7},{2, 6}or {3,5} so there are 3 ways. But seems the above math doesn't give the same answer. Anything I miss here? Thanks. –  user1285419 Jun 16 at 15:33

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.