the numbers of solution

Let's build up to the full problem. Below, $a_1,a_2,a_3,a_4$ will always be non-negative integers (the summands); $n$ will be a non-negative integer target. Let $f_k(n)$ be the number of solutions to the equation $a_1 + \cdots + a_k = n$ .

Clearly, $f_1(n)=1$ .

How many solutions are there to $a_1+a_2=n$ ? We can pick any value from $0$ to $n$ inclusive for $a_1$ , and then $a_2=n-a_1$ will work; so $f_2(n)=n+1$ .

By extending this logic we find, in general, $f_k(n)=\sum_{r=0}^n f_{k-1}(n-r) = \sum_{r=0}^n f_{k-1}(r)$

So $f_3(n)=\frac12 (n+1)(n+2)$ .

For example, there are $231$ solutions to $a_1+a_2+a_3=20$ .

How does this help with $a+b+c+4d=20$ ? Well, note that $0\le d \le 5$ ; we can just rewrite the equation as $a+b+c=20-4d$ and use the above result to find the number of solutions is $f_3(20)+f_3(16)+f_3(12)+\cdots + f_3(0) = 231+153+91+45+15+1=\boxed{536}$ .

In general, the number of solutions to $a+b+c+4d=4m$ is given by $\sum_{d=0}^m f_3 (4d) = \frac13 (1 + m) (3 + 13 m + 8 m^2)$

Some bonus questions:

• what if the target $n$ is not a multiple of $4$ ?

• can you find a closed formula for the number of solutions to $a+b+c+4d=n$ for all non-negative $n$ ?

• are these formulas always polynomials?

• if so, what degree are these polynomials, and why?

1
2
3
4
5
6
7
8

j=0
for a in range(0,21):
    for b in range(0,21):
        for c in range(0,21):
            for d in range(0,21):
                if ((a+b+c+4*d)==20):
                    j+=1
print (j)

1

536

I wish to know the proper way to solve, because I couldn't find any.