I've already done a few problems such as this, other problems where I'm supposed to find the number of combinations or permutations, subject to certain restrictions. Here's been my basic strategy:
- Find $A$ = the number of total solutions (combinations) were there no restrictions.
- Find $B$ = the number of illegal solutions (solutions that violate the restriction)
- Give $A-B$ as the answer.
That may or may not be the best general strategy - it certainly produces some ugly messes of equations sometimes, but I think it's basically sound. The problem occurs when there are large inequalities (i.e., "where $x_3<10$" or something), where you have to then count every single case that satisfies that restriction, or alternatively every single case that violates it, necessitating a big stream of inelegant calculation. That alone, while annoying, is OK as long as I'm sure I'm right.
The thing is, in this case I'm not sure if I can apply it here - or at least I'm not sure if I'm applying it correctly. Here's the specific problem:
Find the number of non-negative solutions to the equation $x_1 + x_2 + x_3 + x_4 + x_5 = 21$ with the restriction that $0\leq x_i\leq 10$ for each $x_i$.
Now, I know that the total number of solutions to an (unrestricted) equation of this form is $\binom{n+k-1}{k-1} = \binom{21+5-1}{5-1} = \binom{25}{4}$. But how do I count violations? I suppose the largest a given $x_i$ could be is 21. Would I then count the number of solutions where a given $x_i$ is 11, then 12, then 13... up to 21? How then would I proceed to when more than one $x$ is greater than 10? Enumerating each combination among up to 5 $x$s at 11 different values each seems to be a nightmarish prospect. Is there some simpler way of looking at the problem that I'm not seeing? Maybe a good general strategy for how to apply a set of restrictions to counting a number of combinations?