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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question

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|cite|improve this answer

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|cite|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. – Gyu Eun Lee Dec 12 '12 at 4:19
Ah. Thanks! @ThomasAndrews – Gyu Eun Lee Dec 12 '12 at 4:26
I make that mistake all the time... – Thomas Andrews Dec 12 '12 at 4:40

This should be the coefficient of $a^{21}$ in
$(1+a+a^2+a^3)(a+a^2+a^3)(a^{15}+a^{16}+a^{17}+a^{18}+...)(1+a+a^2+a^3+a^4+...)^2$ where $a$ is some real $0<a<1$

= coefficient of $a^5$ in

= coefficient of $a^5$ in

= coefficient of $a^5$ in
$(1-a^4 - a^3 + a^7)(1-a)^{-6}$

= coefficient of $a^5$ in
$(1-a^4 - a^3 + a^7)(1+6a+\frac{6.7}{2!}a^2 +\frac{6.7.8}{3!}a^3 +\frac{}{4!}a^4 + ... )$

$= \frac{}{5!} - 6 - \frac{6.7}{2!}$

share|cite|improve this answer

Your Answer


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.