# Non-negative integers to form a sum with restrictions? [duplicate]

How do I solve this?

Number of non-negative solutions to $x_1 + x_2 + x_3 + x_4 = 4$ where $0 \le x_i \le 3$?

What's the general technique? I already know the technique for $j \le x_i$ but have no clue about upper bound restrictions.

• In the example the conditions $x_i\leq3$ exclude exactly $4$ solutions. I suppose you want to have something for more general RHS values. What do you mean by $j\leq x_i$? – Marc van Leeuwen Jan 12 '15 at 15:22
• j is a nonnegative integer. I know how to deal with lower bounds for $x_i$. – Haresh Jan 12 '15 at 15:25
• Lower bounds for $x_i$ are easy; just give every variable its minimum (lower bound) and use a new variable for what remains. But this seems unrelated to the current problem. – Marc van Leeuwen Jan 12 '15 at 15:29

If you compute the polynomial $(1+X+X^2+X^3)^4$ then the coefficient of $X^n$ will be the number of solutions to the problem with right hand side $n$ (so $n=4$ gives your answer $31$ here).
This is effectively a simple form of selection from a multiset. The general version would have varying limits for each $x_i$. You can use an inclusion-exclusion approach to enumerate the possibilities:
Obviously in this case we are only removing the $x_i= 4$ cases so a simpler argument can be used.