5
$\begingroup$

The Frobenius equation is the Diophantine equation $$ a_1 x_1+\dots+a_n x_n=b,$$ where the $a_j$ are positive integers, $b$ is an integer, and a solution $$(x_1, \dots, x_n)$$ must consist of non-negative integers, i.e. $$ x_j \in \mathbb{N} $$ as Natural numbers. For negative $b$, there are no solutions.

  • My question: Is there any known formula that counts the number of solutions, by giving $a_1, \dots, a_n$, $b$, and $n$? Let us call this function as $F (a_1, \dots, a_n; b, n)$, what is known for this:

    $$F (a_1, \dots, a_n; b, n)=?$$

For all the $a_j=1$, we can simplify the above Frobenius equation to: $$ x_1+\dots+x_n=b, \tag{1}$$ where $b \in \mathbb{Z}^+$ is a positive integer.

  • Here is another simpler question: Is there a general formula for Eq.(1) counting all the possible solutions $$(x_1, \dots, x_n)$$
    for given the positive integer $n \in \mathbb{Z}^+$ and $b \in \mathbb{Z}^+$? This should be related to the Partition, but I am not sure the exact forms are known? Say, can we find the total number of soultions as a function $f(n,b)$, and what is $$ f(n,b)=? $$

It seems the answer is known:

$$ f(n,b)= \binom{b+n-1}{n-1}. $$

p.s. Sorry if this question is too simple for number theorists. But please provide me answer and Refs if you already know the answer. Many thanks!

$\endgroup$
5
$\begingroup$

As usual, it depends on what you call a "formula". There are several approaches used to study the general equation: numerical semigroups, Fourier analysis, partial fraction decomposition, generating funtions, counting lattice point in polytopes, multiple zeta functions, etc.

For $n=2$ (and $a_1$, $a_2$ relatively prime) there is a simple formula, namely

$$F(a_1,a_2;b,2)=\frac{b}{a_1a_2} +\left\{\frac{{a_2}^{-1}b}{a_1}\right\} +\left\{\frac{{a_1}^{-1}b}{a_2}\right\}+1,$$ where ${a_1}^{-1}$ is an inverse modulo $a_2$, ${a_2}^{-1}$ is an inverse module $a_1$, and $\{x\}$ denotes the fractional part of $x$. There is no known similar formula for $n\ge3$ (and there is probably no hope in finding a simple one). In the simplest case $a_i=1$ for all $i$, your formula is correct.

There is a beatiful book that discusses this topic in Chapter 1: "Computing the continuous discretely" by Beck and Robins. Also, as a reference, you may look at any book about "Numerical semigroups".

(There are several people in MO that are far better qualified at answering this, and I hope they will see your question and answer it.)

$\endgroup$
  • $\begingroup$ thanks +1, this is helpful $\endgroup$ – wonderich Feb 10 at 18:11
3
$\begingroup$

$F(a_1,\dots,a_n;b)$ equals the coefficient of $z^b$ in the generating function $$f(z):=\frac{1}{1-z^{a_1}}\frac{1}{1-z^{a_2}}\cdots \frac{1}{1-z^{a_n}}.$$

For a fixed choice of $a_1,\dots,a_n$, explicit formula for $F(a_1,\dots,a_n;b)$ as a function of $b$ can obtained via partial fraction decomposition.

For the second question, see Stars and bars.

$\endgroup$
  • $\begingroup$ thanks +1 for the short formula and refs. $\endgroup$ – wonderich Feb 12 at 4:27
3
$\begingroup$

You can take generating function $$f(z):=\frac{1}{1-z^{a_1}}\frac{1}{1-z^{a_2}}\cdots \frac{1}{1-z^{a_n}}$$ as in Max Alekseyev's answer and calculate $F (a_1, \dots, a_n; b, n)$ as $$ \frac{1}{2 \pi i} \int_{|s|=\rho} f(s) \frac{d s}{s^{b+1}} \quad (0<\rho<1). $$ It gives the answer $$ F (a_1, \dots, a_n; b)=\frac{b^{n-1}}{(n-1) ! a_{1} \ldots a_{n}}+\sum_{k=0}^{n-2} c_{k} b^{k}. $$ It is a classical applications of contour integration taken from the book "Residues and their applications" by A.O. Gelfond (1966, pp. 98-99, Russian). If $(a_j,a_k)=1$ ($j\ne k$) then all poles (excepting $s=1$) are simple and formula can be simplified: $$ F (a_1, \dots, a_n; b)=\frac{(-1)^{n-1}}{(n-1) !} \frac{d^{n-1}}{d s^{n-1}}\left[s^{-b-1} \prod_{k=1}^{n} \frac{1-s}{1-s^{a_{k}}}\right]_{s=1}+R $$ where $|R|<C$ for some constant $C$.

$\endgroup$
2
$\begingroup$

Some number theory terminology for your second question is the number of integer compositions of $b$ with $n$ parts, where the parts are required to be positive integers. There are $\binom{b-1}{n-1}$ of these: think of having $b$ 1s in a row and, among the $b-1$ spaces between them, placing $n-1$ plus signs. Combine the adjacent 1s and separate parts by +, e.g., $11+1+1+11 \sim 2+1+1+2$ is one of the $\binom{5}{3}=10$ 4-part compositions of 6.

By the way, integer partitions are equivalent to solutions where the order of the summands does not matter. Equivalently, if the summands are placed in a specified order, typically nonincreasing. For example, $2+1+1+2$ and $1+2+1+2$, etc., would all correspond to $2+2+1+1$. There are generally fewer partitions than compositions and there is not such a simple formula for the number of them.

Your formula, $\binom{b+n-1}{n-1}$, is for the number of compositions with nonnegative integer parts. The "stars & bars" argument in combinatorics verifies the formula: Any arrangement of $b$ 1s and $n-1$ plus signs gives one of these compositions, e.g., $1111+11++ \sim 4+2+0+0$ is one of the $\binom{9}{3} = 84$ 4-part weak compositions of 6.

As @EFinat-S wrote, there's a nice formula for two variables, but for arbitrary linear Diophantine equations, there is nothing like that. The end of Beck & Robbins chapter 1 touches on this (e.g., the "chicken McNugget problem") and goes on to more advanced approaches---it's a great book.

$\endgroup$
  • $\begingroup$ thanks +1, this is good. $\endgroup$ – wonderich Feb 12 at 4:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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