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.
3
-
$\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 LeeuwenCommented Jan 12, 2015 at 15:22
-
$\begingroup$ j is a nonnegative integer. I know how to deal with lower bounds for $x_i$. $\endgroup$– HareshCommented Jan 12, 2015 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 LeeuwenCommented Jan 12, 2015 at 15:29
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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).
answered Jan 12, 2015 at 15:27
$\begingroup$
$\endgroup$
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.
