Number of non-negative integer constraint solutions to simple linear equations

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?

• 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. – mathreadler Dec 21 '17 at 12:17

1 Answer

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.