4
$\begingroup$

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?

$\endgroup$
0

2 Answers 2

10
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Yes, I would like to include the case $x_i = 0$. $\endgroup$ Oct 30, 2011 at 18:32
  • $\begingroup$ In this cases what you are looking for should be exactly the denumerant. $\endgroup$
    – user9072
    Nov 2, 2011 at 20:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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