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?

  • $\begingroup$ Do you know how to find the solutions in which some of the variables are greater than $10$? If that's the case I would try inclusion-exclusion. $\endgroup$ – EuYu Nov 5 '12 at 4:00
  • $\begingroup$ Can you give me a little more information? I've encountered the generalized inclusion-exclusion principle but I'm not sure how I would apply it here. $\endgroup$ – limp_chimp Nov 5 '12 at 4:05
  • $\begingroup$ Let me write something up. $\endgroup$ – EuYu Nov 5 '12 at 4:05
  • 3
    $\begingroup$ In addtion to @EuYu’s write-up, you might want to look here. See also this answer and this one. $\endgroup$ – Brian M. Scott Nov 5 '12 at 4:07
  • 1
    $\begingroup$ Weeding out the "bad" ones can be painful. Here we are helped a lot by the fact that if some $x_i$ is $\ge 11$, there is only one. It would be much worse if instead of $21$ we had, say, $35$. $\endgroup$ – André Nicolas Nov 5 '12 at 4:18

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!

| cite | improve this answer | |
  • $\begingroup$ :with $x_i>=11$ if the substitutions are made as $y_i=x_i-11$ for all $i$ then the problem is equivalent to $y_1+11+y_2+11+...+y_5+11=21$.But this gives a negative value to the right hand side?$\binom{14}{4}$ is made considering only one x and it is later multiplied by 5.But what's wrong with the way I am doing it $\endgroup$ – clarkson Oct 14 '14 at 8:52

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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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