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.

How many solutions are there to the equation: $$x_1 + x_2 + x_3 + x_4 + x_5= 21\;,$$ where $x_i$ is a non-negative integer such that $$0 \le x_1 \le 3;\; 1 \le x_2 < 4;\text{ and }x_3 \ge 15\;?$$

share|improve this question
add comment

3 Answers

I like to think of such problems in terms of putting identical marbles into distinguishable boxes. Here there are $21$ marbles to be distributed amongst $5$ boxes, and $x_k$ is the number of marbles in box $k$. We first ensure that box $3$ gets at least $15$ marbles and box $2$ at least $1$ marble by simply putting $15$ marbles into box $3$ and $1$ into box $2$; this leaves $21-15-1=5$ marbles to be distributed amongst the $5$ boxes. If you like, you can think of this as replacing $x_2$ by $x_2'=x_2-1$ and $x_3$ by $x_3'=x_3-15$, and counting solutions to $$x_1+x_2'+x_3'+x_4+x_5=5\tag{1}$$ subject to the condition that all five unknowns be non-negative integers, with $x_1\le 3$ and $x_2'<3$.

Now use the standard stars-and-bars calculation to find the number of unrestricted solutions to $(1)$ in non-negative integers; it’s explained quite well in the linked article. Then use an inclusion-exclusion calculation to subtract the unwanted solutions, i.e., those with $x_1>3$ or $x_2\ge 3$. This will be fairly easy, since it’s impossible for $x_1$ and $x_2$ to be too large simultaneously.

In case you’ve not done anything like this before, counting the solutions with $x_1>3$ is simply counting those with at least $4$ marbles in box $1$ to begin with: you deal with this restriction exactly as I dealt with the original lower bounds on $x_2$ and $x_3$.

share|improve this answer
add comment

There is also the generating functions approach. Here the generating functions for each variable would be:

$x_1: 1+x+x^2+x^3$

$x_2: x + x^2 + x^3$

$x_3: \sum_{n=15}^\infty x^n$

Others: $\sum_{n=0}^\infty x^n$

Multiply these generating functions together, find the generating function for the problem, and compute the coefficient of $x^{21}$.

share|improve this answer
    
Unfortunately I've got no idea if you've covered generating functions or not. But I find this class of problems is relatively hard via any other method if you have an upper bound on these variables. –  kigen Dec 12 '12 at 4:19
    
Ah. Thanks! @ThomasAndrews –  kigen Dec 12 '12 at 4:26
    
I make that mistake all the time... –  Thomas Andrews Dec 12 '12 at 4:40
add comment

First,note that you can rewrite the problem as trying to find $y_1,...,y_5$ with $$y_1+y_2+y_3+y_4+y_5=6$$ with $y_i>=0$ and $y_1\leq 3$, $y_2\leq 3$. Then you get a solution with $x_1=y_1$, $x_2=y_2+1$, $x_3=y_3+15$, $x_4=y_4$ and $x_5=y_5$.

This can then be computed as:

$$\sum_{i=0}^3\sum_{j=0}^3 \binom{8-i-j}{2}=4\binom{5}{2}+3\left(\binom{6}{2}+\binom{4}2\right)+2\left(\binom{7}{2}+\binom 3 2\right) + \left(\binom{8}2+\binom2 2\right)$$

share|improve this answer
add comment

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.