Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

Questions on MathOverflow are expected to relate to research level mathematics within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here. If this question can be reworded to fit the rules in the help center, please edit the question.

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

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