How many integer solutions to a linear combination, with restrictions?

Question

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:

1. Find $A$ = the number of total solutions (combinations) were there no restrictions.
2. Find $B$ = the number of illegal solutions (solutions that violate the restriction)
3. 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?

Answer 1

You've counted the general non-negative solutions to the equation. Now suppose that we want to count the number of solutions in which $x_1 > 10$. This is the same as counting the number of non-negative solutions to $$(x_1 - 11) + x_2 + \cdots + x_5 = x_1' + x_2 + \cdots + x_5 = 10$$ Now if you can repeat this process for each variable and for each combination of variables (most are trivial) and if you then apply the principle of inclusion and exclusion, we can filter out the solutions in which the the variables are larger than $10$.

This is explained in much better detail in Brian's excellent answer linked in the comments.

Answer 2

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!