# How to count the number of solutions to linear Diophantine equation with multiple variables recursively?

Consider the diophantine equation of the form $$a_1x_1+a_2x_2+\cdots +a_kx_k=n$$ where $$n,k\geq 1$$ and $$a_i$$ are non-negative integers. Then we are concerned $$v(n)$$ denote the number of solutions for a fixed tuple $$(a_1,a_2,\cdots ,a_k).$$ Can $$v(n)$$ be expressed recursively, that is, in terms of $$v(n-1),v(n-2),$$ etc?

I considered the following example to see if I could generalize $$x_1+2x_2 = n.$$ I noticed that if $$(x_1,x_2)$$ is a solution of $$x_1+2x_2 = n-k$$ then $$(x_1+k,x_2)$$ is a solution of $$x_1+2x_2=n.$$ Furthermore for $$k=2p$$ then if $$x_1+2x_2 = n-k=n - 2p$$ then $$(x_1,x_2+p)$$ is a solution of $$x_1+2x_2=n.$$ Therefore, $$v(n) = \sum_{k=1}^{n}v(n-k)+v(n-2)+v(n-4)+\cdots$$

Is this correct? How do I get a general formula for $$v(n)?$$ Any ideas will be much appreciated?

• Are the $x_k$ to be any integers? (then infinitely many solutions can happen), or are the $x_k$ to be non-negative? Dec 29, 2018 at 22:27
• $x_k$ are non-negative. Dec 29, 2018 at 22:48
• In your formula, in the sum part are many terms which coincide with the extra terms after the sum. Have you tried your formula in some cases of reasonably small $n$? It would be good to include them. [I assume the extra terms are restricted so no terms $v( \rm{negative})$ occur.] Dec 30, 2018 at 0:37
• Yeah, I will try that. In the meantime I found this: nipne.ro/rjp/2013_58_9-10/1408_1417.pdf Refer to page 2. I think it is interesting. Dec 30, 2018 at 0:48
• Yes, that link of your comment seems to be to a proven recurrence. Dec 30, 2018 at 1:07

Let's denote with $$v(k,n)$$ the number of solutions of the following equation:

$$a_1x_1+a_2x_2+\cdots +a_kx_k=n$$

Take a look at the last item $$x_k$$. It can take any value from 0 to $$\lfloor{\frac{n}{a_k}}\rfloor$$. So we have the following recurrence relation:

$$v(k,n)=\sum_{i=0}^{\lfloor{\frac{n}{a_k}}\rfloor} v(k-1,n-i\cdot a_k)\tag{1}$$

...with the following exit criteria:

$$v(1,n)=\begin{cases} 1, & \text{if}\ a_1\mid n \\ 0, & \text{if}\ a_1\nmid n \end{cases}$$

Here is an example: let's count the number of solutions for the following equation:

$$x_1+2x_2+3x_3+2x_4+6x_5+2x_6=100$$

You can do this in Java:

public class SolutionCounter {
public static int count(int[] a, int k, int n) {
if(k == 1) {
return (n % a[0] == 0)? 1: 0;
}
int cnt = 0;
for(int i = 0; i <= n / a[k - 1]; i++) {
cnt += count(a, k - 1, n - i * a[k - 1]);
}
return cnt;
}

public static void main(String[] args) {
int[] a = {1,2,3,2,6,2};
int sum = 100;
int cnt = count(a, a.length, sum);
System.out.println(cnt);
}

}


or with this ridiculously short Python script:

def cnt(a, k, n):
if k == 1:
return 1 if n % a[0] == 0 else 0
return sum(cnt(a, k - 1, n - i * a[k - 1]) for i in range(0, int(n / a[k - 1]) + 1))

print(cnt([1,2,3,2,6,2], 6, 100))


...and the result is: 847875.

• Could you give a recurrence in terms of $n$? Jan 2, 2019 at 9:31
• (1) already gives recurrence formula for $v(n)$ in terms of $v(n-1)$, $v(n-2)$,... but you must also take values of $a_i$ into account. I doubt that simpler recurrence formula exists.
– Saša
Jan 2, 2019 at 10:54
• Say you have $x_1+2x_2=n$ and the number of solutions to this is $v(n).$ Is there a way to express $v(n)$ in terms of $v(1),v(2),\cdots,v(n-1)?$ In your recurrence, it like you are conditioning on one variable and therefore getting rid of a term. Whereas I want to condition on $n$. I hope this makes sense? Jan 2, 2019 at 11:00
• @Hello_World Can you explain your request on the simplest possible example: $4x_1=n$. What is the recurrence formula for $v(n)$ in this simplest case? If we don't find a cute formula for one variable, chances are we won't find it for many more.
– Saša
Jan 2, 2019 at 11:20