Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

We're given the following equation:

$$x_1 + x_2 + x_3 + x_4 + x_5 = 20$$

I know that the simple amount of solutions to this is $\binom{5+20-1}{5-1}$, but for the following questions I'm slightly more confused. How would I find the number of solutions for these?

Note that $x_i$ must be non-negative.

a) So $x_i\geq 1$ for $1 \leq i \leq 5$.

b) So $x_i\geq 2$ for $i=1,2$ and $x_i\geq 3$ for $i=3,4,5$.

c) So $x_3 < 12$.

I'm just really confused how I'd do it with restrictions.

I know the formula for just the general number of solutions without any restrictions is $\binom{n + k - 1}{n - 1}$ but how would I apply that WITH restrictions?

share|improve this question

2 Answers 2

up vote 2 down vote accepted

(b) You want the number of solutions of $$x_1+x_2+x_3+x_4+x_5=20\tag{1}$$ in non-negative integers satisfying $x_1,x_2\ge 2$ and $x_3,x_4,x_5\ge 3$. Let

$$\begin{align*} &y_1=x_1-2,\\ &y_2=x_2-2,\\ &y_3=x_3-3,\\ &y_4=x_4-3,\text{ and}\\ &y_5=x_5-3\;. \end{align*}$$

Then $\langle x_1,\dots,x_5\rangle$ is a solution to $(1)$ meeting the extra conditions if and only if $\langle y_1,\dots,y_5\rangle$ is a solution in non-negative integers to

$$y_1+y_2+y_3+y_4+y_5=7\;.\tag{2}$$

If you’ve seen the interpretation of the original problem as counting the number of ways to put $20$ indistinguishable balls into $5$ distinguishable boxes subject to the condition that the first two boxes each contain at least $2$ balls and the others at least $3$, the new problem is what you get if you put the minimum requirement into each box and then ask how many ways there are to distribute the remaining $7$ balls without any restrictions.

Now you can use the formula that you know for the unrestricted case to get a total of $$\binom{7+5-1}{5-1}=\binom{11}4$$ solutions.

You can use the same basic technique to solve (a) or any other such problem when the restrictions are all lower bounds.

For (c) and other problems with upper bounds you’ll want an inclusion-exclusion argument. In this problem it’s not at all bad. First count the number of unrestricted solutions, and then subtract the number of ‘bad’ solutions, i.e., the number that have at $x_3\ge 12$. Note that counting these ‘bad’ solutions is a problem with lower bounds, so you now know how to handle it. The problem would be a bit messy if it were possible to violate more than one upper bound, but it’s not, since you have only one upper bound to worry about.

share|improve this answer
    
I'm confused for (c). Would I not just do $all - (x_3 >= 12)$? I thought the inclusion-exclusion principle applied to the union of two sets. If I did the union of all and $x_3 >= 12$ would I not just get all, as all encompasses the other ones? –  Doug Smith Jan 28 '13 at 14:04
    
@Doug: In this $x_3\ge12$ is the only case that needs to be excluded, so it does boil down to subtracting these from the total; that’s exactly what I suggested. But this is a very simple example of an inclusion-exclusion argument; it’s just that all of the correction terms other than the $x_3\ge12$ one are zero. (Inclusion-exclusion is by no means limited to unions of two sets.) For a more general example in which more calculation is needed, see my answer to this question. –  Brian M. Scott Jan 28 '13 at 19:10

Hint:

If you use stars and bars to develop your original expression then (a) and (b) use essentially the same method except that some stars are stuck next to a bar (or the start) and so can come out of the calculation.

For (c), do the same thing to calculate the number of solution with the restriction $x_3 \ge 12$, and combine this with your original expression.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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