4
$\begingroup$

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?

  • 0
    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.2012-11-05
  • 0
    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.2012-11-05
  • 0
    Let me write something up.2012-11-05
  • 0
    Somewhat irrelevant comment: if you are lazy you can apply generating functions to get the answer mechanically.2012-11-05
  • 3
    In addtion to @EuYu’s write-up, you might want to look [here](http://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle). See also [this answer](http://math.stackexchange.com/a/203839/12042) and [this one](http://math.stackexchange.com/a/146489/12042).2012-11-05
  • 0
    Also note that in certain cases, e.g. if you replace the 21 with 42, you can take a shortcut: Give every $x_i$ a value of 10, so we have a total of 50. Now we have 8 too many, so distribute 8 among the $x_i$s. This gives us an answer of $\binom{12}{4}$, and is related to the fact that $\sum_k (-1)^k \binom{n}{k} p(k) = 0$ if $p(k)$ is a polynomial of degree less than $n$.2012-11-05
  • 1
    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$.2012-11-05

2 Answers 2