Suppose we want to find the number of non-negative integral solutions to the equation:

$$x_1 + x_2+ x_3 = m$$

where we have $x_i \le L_i, i\ge2$

I found the solution as:

$$\sum_{x_2=0}^{L_2} \sum_{x_3=0}^{L_3} \frac{m!}{x_2!x_3!(m-x_2-x_3)!}$$

My questions are two-fold:

  • Is my answer correct?

  • This solution is computationally impossible for $m=100$, for example. Can somebody provide the answer in a computable format?

  • $\begingroup$ The equation is a planes equation. I think there is something called lattices for integer linear stuff, but I don't know much about them. Maybe it can help you though. $\endgroup$ – mathreadler Dec 21 '17 at 12:17

Hint for partial checks on your solution:

If $\ \ \forall i\in\langle 1,r\rangle \ \ \ L_i = m \quad,$ then the number of non-negative solutions (that is,$\ \ 0 \le x_i \le m)$

to the equation $\quad "x_1 +x_2 + x_3 + \cdots + x_r=m" \ \ is \ \ {m+r-1\choose r-1}$

I would say if your solution does not meet this test then it is not right.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.