[Math] Generalized permutation and combination: number of solutions

combinatorics

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

Best Answer

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

Related Question