Question

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

Answer 1

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

Answer 2

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