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$

  • $\begingroup$ not sure the combinatorics tag is needed ... the example has a countably infinite number of solutions on the integers, $\endgroup$
    – user451844
    Sep 20, 2017 at 10:47
  • $\begingroup$ Oh... We can use only positive integers. $\endgroup$ Sep 20, 2017 at 10:49
  • $\begingroup$ 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. $\endgroup$
    – user451844
    Sep 20, 2017 at 10:51
  • $\begingroup$ Yes, thanks. I added this condition. $\endgroup$ Sep 20, 2017 at 10:52

1 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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .