Request for an exact formula related to a partition in number theory

Question

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!

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

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.