Number of combinations to sum two specific numbers to match a target I have a result number M and two numbers N1 and N2. My goal is to calculate how many ways can I create the number M from numbers N1 and N2.
Examples:
M1 = 100
N1 = 10, N2 = 13

Options:
= 10 * 10 + 13 * 0
Combinations: 1
---------------------

M=749
N1=10, N2=13

Options
= 10 * 32 + 13 * 33
= 10 * 19 + 13 * 43
= 10 * 6 + 13 * 53
= 10 * 71 + 13 * 3
= 10 * 58 + 13 * 13
= 10 * 45 + 13 * 23
Combinations: 6

I've tried floor(M/lcm(N1, N2))+1 but that is sometimes 1 off (but the +1 makes sure it's 90% right) and sometimes it's completely wrong, for example for M=21157, N1=39, N2=36 (it says 46 options but there are actually none)...
Any ideas how to solve that?
 A: This is a (fairly) difficult problem, sometimes referred to as a change-making problem, and a nice closed form is not known (to my knowledge).  However, we can express the answer in terms of a generating function.  If you give me two positive integers $a$ and $b$, define $f_{a,b}(n)$ to be the number of ways to express $n$ as a sum of (non-negative) integer multiples of $a$ and $b$.  The generating function corresponding to this sequence is defined as $F(x) = \sum\limits_{n = 0}^\infty f_{a,b}(n) x^n.$  Then we have $$F(x) = \sum\limits_{n = 0}^\infty f_{a,b}(n) x^n = \sum\limits_{i,j \geq 0}  x^{ia + jb} = \left( \sum\limits_{i\geq 0}  x^{ia}\right)\left( \sum\limits_{j\geq 0}  x^{jb}\right) = \frac{1}{(1 - x^a)(1 - x^b)}.$$
Thus, we can say $f_{a,b}(n)$ is the coefficient of $x^n$ in $\frac{1}{(1 - x^a)(1 - x^b)}$.  In your case, you were looking for the coefficient of $x^{749}$ in $\frac{1}{(1 - x^{10})(1 - x^{13})}.$  
It's not a nice closed-form, but it's the best that combinatorics can do for this problem.  There's a theorem that tells us how $f_{a,b}(n)$ behaves for very large $n$, but unfortunately we can't get an exact answer from a nice closed form.
A: *

*I don't know if you came accross that but try these steps:


1- Try to figure one simple solution of the diophantine equation: $M1=N1*k1+N2*k2$
2- Extract the PGCD pf $N1$ and $N2$ which is $N$
3- Number of solutions of the equation $M1=N*(n1*k1+n2*k2)$ is:
$floor(\frac{k2}{n1})+floor(\frac{k1}{n2})+1$
