# How to find all combinations that equal a given sum

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$

• not sure the combinatorics tag is needed ... the example has a countably infinite number of solutions on the integers, – user451844 Sep 20 '17 at 10:47
• Oh... We can use only positive integers. – Piotr Wasilewicz Sep 20 '17 at 10:49
• 0 is technically non-negative not positive, but okay that should be put in the question otherwise a+c=3 has a countably infinite number of solutions. – user451844 Sep 20 '17 at 10:51
• Yes, thanks. I added this condition. – Piotr Wasilewicz Sep 20 '17 at 10:52

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