Number of solutions of $ax+by+cz=n$ in nonnegative integers

124 Views Asked by At

Let $a,b,c,n\in\mathbb{Z}_0^+$. The number of solutions of $$ax+by+cz=n$$ (i.e. the number of ordered triplets $(x,y,z)$ satisfying the equation) in $\mathbb{Z}_0^+$ as a function of $n$ is $$\frac{1}{n!}\lim_{w\to 0}\frac{d^n}{dw^n}\frac{1}{(1-w^a)(1-w^b)(1-w^c)}=\frac{1}{2\pi i}\oint \frac{dw}{(1-w^a)(1-w^b)(1-w^c)w^{n+1}}$$ by the theory of generating functions and Cauchy's integral formula.

If $a,b,c$ are small, then the $n$th derivative/contour integral is amenable for computation using partial fraction decomposition. But for large $a,b,c$, the partial fraction decomposition becomes very tedious.

Are there any faster methods of computing this particular integral, or faster methods of obtaining the number of solutions in general?

1

There are 1 best solutions below

2
On BEST ANSWER

The topic is standardly known as the Frobenius coin problem, and it is quite complicated in general.

In the 2D case $ax+by=n$ there is an interesting theorem, the Popovicius' theorem which tells that the number of non-negative solutions $ p_{\left\{ {a,b} \right\}} (n)$ is given by

$$ \eqalign{ & p_{\left\{ {a,b} \right\}} (n) = \left| {\,\left\{ \matrix{ 0 \le x,y,a,b,n \in Z \hfill \cr \gcd (a,b) = 1 \hfill \cr ax + by = n \hfill \cr} \right.\;} \right| = \cr & = {n \over {ab}} - \left\{ {{{b^{\,\left( { - 1} \right)} n} \over a}} \right\} - \left\{ {{{a^{\,\left( { - 1} \right)} n} \over b}} \right\} + 1 \cr} $$ where $$ \left\{ x \right\} = x - \left\lfloor x \right\rfloor \quad b^{\,\left( { - 1} \right)} b \equiv 1\;\left( {\bmod a} \right) \quad a^{\,\left( { - 1} \right)} a \equiv 1\;\left( {\bmod b} \right) $$

For the 3D case, like the present, we can apply the above to $ax+by=n-cz$ and sum over $z$. $$ \eqalign{ & p_{\left\{ {a,b,\,c} \right\}} (n)\quad \left| {\; \gcd(a,b) = 1} \right.\quad = \sum\limits_{z = 0}^{\left\lfloor {n/c} \right\rfloor } {p_{\left\{ {a,b} \right\}} (n - cz)} = \cr & = \sum\limits_{k = 0}^{\left\lfloor {n/c} \right\rfloor } {\left( {{{n - ck} \over {ab}} - \left\{ {{{b^{\,\left( { - 1} \right)} \left( {n - ck} \right)} \over a}} \right\} - \left\{ {{{a^{\,\left( { - 1} \right)} \left( {n - ck} \right)} \over b}} \right\} + 1} \right)} = \cr & = {n \over {ab}}\left( {\left\lfloor {{n \over c}} \right\rfloor + 1} \right) - {c \over {2ab}}\left\lfloor {{n \over c}} \right\rfloor \left( {\left\lfloor {{n \over c}} \right\rfloor + 1} \right) + \left( {\left\lfloor {{n \over c}} \right\rfloor + 1} \right) + \cr & - \sum\limits_{k = 0}^{\left\lfloor {n/c} \right\rfloor } {\left( {\left\{ {{{b^{\,\left( { - 1} \right)} \left( {n - ck} \right)} \over a}} \right\} + \left\{ {{{a^{\,\left( { - 1} \right)} \left( {n - ck} \right)} \over b}} \right\}} \right)} = \cr & = \left( {{n \over {ab}} - {c \over {2ab}}\left\lfloor {{n \over c}} \right\rfloor + 1} \right) \left( {\left\lfloor {{n \over c}} \right\rfloor + 1} \right) - \sum\limits_{k = 0}^{\left\lfloor {n/c} \right\rfloor } {\left( {\left\{ {{{b^{\,\left( { - 1} \right)} \left( {n - ck} \right)} \over a}} \right\} + \left\{ {{{a^{\,\left( { - 1} \right)} \left( {n - ck} \right)} \over b}} \right\}} \right)} \cr} $$

Example:

$$n=13, \, a=3, \, b=4, \, c=5$$ the solutions are $$ \left( {x,y,z} \right) \in \left\{ {\left( {0,2,1} \right),\left( {1,0,2} \right),\left( {3,1,0} \right)} \right\} $$ The modular inverses of $a$ and $b$ are $$ \eqalign{ & 3 \cdot 3 \equiv 1\left( {\bmod 4} \right) \Rightarrow a^{\,\left( { - 1} \right)} = 3 \cr & 1 \cdot 4 \equiv 1\left( {\bmod 3} \right) \Rightarrow b^{\,\left( { - 1} \right)} = 1 \cr} $$ and $p_{\left\{ {a,b,\,c} \right\}} (n)$ becomes $$ \eqalign{ & p_{\left\{ {3,4,5} \right\}} (13) = \cr & = \left( {{{13} \over {12}} - {5 \over {24}}\left\lfloor {{{13} \over 5}} \right\rfloor + 1} \right) \left( {\left\lfloor {{{13} \over 5}} \right\rfloor + 1} \right) - \sum\limits_{k = 0}^2 {\left( {\left\{ {{{\left( {13 - 5k} \right)} \over 3}} \right\} + \left\{ {{{3\left( {13 - 5k} \right)} \over 4}} \right\}} \right)} = \cr & = 5 - \sum\limits_{k = 0}^2 {\left( {\left\{ {{{13} \over 3}} \right\} + \left\{ {{{39} \over 4}} \right\} + \left\{ {{8 \over 3}} \right\} + \left\{ {{{24} \over 4}} \right\} + \left\{ {{3 \over 3}} \right\} + \left\{ {{9 \over 4}} \right\}} \right)} = \cr & = 5 - \sum\limits_{k = 0}^2 {\left( {{1 \over 3} + {3 \over 4} + {2 \over 3} + {1 \over 4}} \right)} = 3 \cr} $$