# finding the combination of sum of M numbers out of N

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?

• You mean how to choose $M$ terms in a set of $N$ numbers? – JoeyBF Jun 16 '14 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 '14 at 14:26

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)$.

• That's so beautiful. Thanks Byron. – user1285419 Jun 16 '14 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.

• does this assure that all m numbers are unique? – user1285419 Jun 16 '14 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 Hidalgo Jun 16 '14 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 '14 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 Hidalgo Jun 16 '14 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 '14 at 15:33