Question

Suppse $n > m$ are positive integers. Then it is an elementary exercise to show that the number of $m$-tuples of non-negative integers $(x_1, \cdots, x_m)$ such that $x_1 + \cdots + x_m = n$ (order matters) is $\binom{n+m-1}{m-1}$. My question is a variant of this, where instead of considering the sum $x_1 + \cdots + x_m = n$ we are consider the weighted sum $w_1 x_1 + \cdots + w_m x_m = n$ for some weight vector $(w_1, \cdots, w_m)$, where $w_i \geq 1, 1 \leq i \leq m$ are co-prime positive integers.

Likely there is no explicit formula as in the case $(w_1, \cdots, w_m) = (1, \cdots, 1)$. However, one might expect that there will be an asymptotic formula. Is there a quick and dirty way to derive such an asymptotic formula?

Answer 1

The quick and dirty way is to regard the weighted sum as counting the number of lattice points $(x_2, ... x_m)$ satisfying $w_2 x_2 + ... + w_m x_m \le n$ and $w_1 | (n - w_2 x_2 - ... - w_m x_m)$. The second condition is satisfied $\frac{1}{w_1}$ of the time. The number of lattice points satisfying the first condition can be approximated by the volume of the corresponding polytope, which is $\frac{n^{m-1}}{w_2 ... w_m (m-1)!}$, so the final asymptotic is $$\frac{n^{m-1}}{w_1 w_2 ... w_m (m-1)!} + O(n^{m-2}).$$

Here is a more rigorous derivation which also provides an "explicit" formula. The number of solutions $a_n$ has generating function $$A(z) = \sum a_n z^n = \frac{1}{(1 - z^{w_1})...(1 - z^{w_m})}$$

and so the asymptotics of $a_n$ are controlled by the behavior of $A(z)$ at the dominant pole $z = 1$, which has multiplicity $m$. The dominant term at this pole is (by l'Hopital's rule for example) $$\frac{1}{w_1 ... w_m (1 - z)^m}$$

and the asymptotic follows. The point here is that one can also sum the contributions from the other poles and, for fixed $w_1, ... w_m$, the result is a completely explicit formula (polynomial-exponential) in $n$. The condition that the $w_i$ are coprime implies that the only pole with a multiplicity of greater than $1$ is $z = 1$, so in fact to get within $O(1)$ one only needs to sum the contributions from $z = 1$ (which, I should add, are very easy to compute in any CAS that can handle power series: one just needs to substitute $x = 1 - z$, multiply by $x^m$, and then compute the first $m$ terms in the resulting series).

Answer 2

Yes, this is a known problem. The quantity is called denumerant, introduced by Sylvester. See an answer of Gerry Myerson or for instance this paper http://math.gmu.edu/~geir/SylvDen2.pdf for more information, including asymtotics.

(I am not certain if this is exactly what you are looking for, as I am not sure whether or not you allow $x_i=0$, as in the cases I link to. But if you don't this is just the same 'shifting' by the sum of the $w_i$.)