How to find all combinations that equal a given sum

Question

Two equations are given:

$a_{1}b_{1} + a_{2}b_{2} + \dots + a_{n}b_{n} = N$

$b_{1} + b_{2} + \dots + b_{n} = M$

and given is set of $a_{1}, a_{2}, \dots a_{n}$

$a_{1}, \dots, a_{n} \geq 0$ and $b_{1}, \dots, b_{n} \geq 0$

How to find all possible equations which satisfy these conditions?

For example:

$a + 2b + c = 5,$

$a+b+c = 4$

We have four combinations: (2,1,1), (1,1,2), (0,1,3), (3,1,0)

Is there any formula for that? What if there will be inequality $ \leq N$

Answer 1

What we've got here is the system of 2 linear equations with $n$ unknown values. To solve it You can use for example the Gauss elimination.

In your example there are solutions with parametric form $$\begin{cases}a=t\\b=1\\c=3-t\end{cases}$$

In general there would be $n-2$ or $n-1$ parameters and there is no easy formula to compute the number of solutions.

There are some special cases when we can easily compute the number of solutions:

• $a_1=...=a_n$ and $N\neq M\cdot a_1$ - then there are no solutions, because the system is conflicted
• $n=2$ and $a_1\neq a_2$ - there is $1$ solution
• $n=2$ and $a_1= a_2$ and $N=M\cdot a_1$ - there are $N$ solutions