2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – Marc van Leeuwen Jan 12 '15 at 15:22
  • $\begingroup$ j is a nonnegative integer. I know how to deal with lower bounds for $x_i$. $\endgroup$ – Haresh Jan 12 '15 at 15:25
  • $\begingroup$ 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. $\endgroup$ – Marc van Leeuwen Jan 12 '15 at 15:29
1
$\begingroup$

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).

$\endgroup$
0
$\begingroup$

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:

  • Calculate the number of combinations as if there were no top limits
  • Calculate the number of combinations that break the constraint for each single variable
  • Calculate the number of combinations that break the constraint for pairs of variables
  • Calculate the number that break the constraint for higher combinations
  • Combine the above results according to the inclusion-exclusion rules

Obviously in this case we are only removing the $x_i= 4$ cases so a simpler argument can be used.

$\endgroup$

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