0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ What partial results have you managed to get? For instance, can you do the cae $a_1=\dots = a_k = 1$? $\endgroup$
    – Yemon Choi
    Nov 3, 2011 at 8:41
  • $\begingroup$ 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. $\endgroup$
    – user9072
    Nov 3, 2011 at 21:08

2 Answers 2

10
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$