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

Question

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?

Answer 1

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.