# Generalized permutation and combination: number of solutions

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\;?$$

-

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$.

-

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}$.

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

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)$$

-

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
$(1+a+a^2+a^3)(1+a+a^2)(1+a+a^2+a^3+a^4+...)^3$

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

= 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{6.7.8.9}{4!}a^4 + ... )$

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

-