Take the 2-minute tour ×

I want to know the exact number of non-negative integer solutions of a1x1+a2x2+...akxk = n ...

I know that it is the co-efficient of x^n in (1-x^a1)^-1 * (1-x^a2)^-1 * ... (1-x^ak)^-1 ...

but whats the co-efficient and how to find the co-efficient ?

Please post the answer at-least even if you don't know the proof of this ...

share|improve this question

closed as off topic by Alex Bartel, Alon Amit, Gjergji Zaimi, Qiaochu Yuan, quid Nov 3 '11 at 21:05


What partial results have you managed to get? For instance, can you do the cae $a_1=\dots = a_k = 1$? –  Yemon Choi Nov 3 '11 at 8:41
Since this is not visible, I voted to close as duplicate of mathoverflow.net/questions/61329 Also the recent mathoverflow.net/questions/79393 is almost a duplicate. –  quid Nov 3 '11 at 21:08

2 Answers 2

From what you wrote, I assume you are considering $n$ and $a_i$ to be positive integers. In this case this equation has a solution if and only if $\gcd(a_1,\ldots,a_k)\mid n$. After removing this common denominator, we may assume that $\gcd(a_1,\ldots,a_k)=1$. In this case, the function $d(n;a_1,\ldots,a_k)$, which counts the number of solutions to this equation, is called the denumerant function of Sylvester. This is related to the famous diophantine problem of Frobenius (see http://en.wikipedia.org/wiki/Coin_problem), which, computationally, is an extremely hard problem.

There is, though, an asymptotics formula for $d(n;a_1,\ldots,a_k)$.

$ d(n;a_1,\ldots,a_k) \approx \dfrac{n^{k-1}}{(k-1)!a_1\ldots a_k} $, as $n\longrightarrow\infty$

Here is an article on this function http://math.gmu.edu/~geir/SylvDen2.pdf, the first google result of "frobenius problem denumerant asymptotic".

share|improve this answer

There's a detailed discussion of your function $d(n;a_1, \dots, a_k$) in Chapters 1 & 8 of a book I wrote with Sinai Robins (and both chapters contain further pointers to the literature, including the Frobenius problem).

share|improve this answer
