# non negative integer solutions : Diophantine Equations [closed]

I want to know the exact number of non-negative integer solutions of $a_1 + 2a_2 + \ldots + k \cdot a_k = n$.

I know that it is the co-efficient of $x^n$ in $(1 - x^{a_1})^{-1} \cdot (1 - x^{a_2})^{-1} \cdot \ldots \cdot (1-x^{a_k})^{-1}$

But what's the coefficient and how to find the coefficient?

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

-

## 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. – user9072 Nov 3 '11 at 21:08

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".

-

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

-