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?
Best Answer
First restrict only so that $x_1 + \cdots + x_5 = 21$ and $x_i \geq 0$ for $i = 1,2,3,4,5$. I.e., first forget about the "cap" on each of the five $x$'s. Then, as you say, there are $\binom{25}{4}$ solutions. Next note that if any one components, let's say $x_1$ for example, is $\geq 11$, then the sum of the others is $\leq 10$. This means each one of the other four components is $\leq 10$ or else at least one is negative, which we've ruled out already. This greatly restricts the complication of the full inclusion-exclusion technique you'd otherwise need to use. Let's count how many of the $\binom{25}{4}$ solutions have a component $\geq 11$. Relabel the numbers so that the offending $x$ is $x_1$. If we define $y_1 = x_1 - 11$, we can write $$y_1 + x_2 +\cdots+x_5 = 10\,,$$ where it still holds that $0 \leq y_1,x_2,x_3,x_4,x_5 \leq 10$. How many solutions of this equation? $\binom{14}{4}$ by the same reasoning as before. We must sutract these solutions from the original $\binom{25}{4}$ solutions because each one of these violated the restriction that $x_1 \leq 10$. We must also subtract the number of solutions with $x_2$,$x_3$, $x_4$ or $x_5$ out of the allowed range. But by the obvious symmetry of the constraints, each one of these is the same as the $x_1$ case. So, the overall number of allowed solutions is $$\binom{25}{4} - 5\times\binom{14}{4}$$.
As an exercise, try counting how many solutions to $x_1 + \cdots x_5 = 22$ lie within $x_1,\ldots,x_5 \leq 10$. If you do it right, the equations don't get too ugly. Good luck and have fun!