Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
add comment

2 Answers

up vote 10 down vote accepted

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

share|improve this answer
add comment

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

share|improve this answer
    
Yes, I would like to include the case $x_i = 0$. –  Stanley Yao Xiao Oct 30 '11 at 18:32
    
In this cases what you are looking for should be exactly the denumerant. –  quid Nov 2 '11 at 20:28
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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