MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|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 Also the recent 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, 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, the first google result of "frobenius problem denumerant asymptotic".

share|cite|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|cite|improve this answer

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