# Number of non-negative integral solutions

This is a problem I've seen a couple times around here, but I couldn't find one quite like this.
Say we have ten variables, $a, b,$ and $c_1, c_2, c_3,\dots, c_8$. How many non-negative integral solutions are there to the following problem such that $a\leq 5$ and $b\geq 5$: $$a+b+c_1 +c_2+c_3 +c_4 +c_5+c_6+c_7+c_8 = 100$$ I understand that the total number of solutions when $a$ and $b$ are unrestrained is ${10+100-1\choose 100}$, but I don't know any real way to formulate these restraints without something like $$\sum_{a=0}^{5}\sum_{b=5}^{100-a}{107 - b-a\choose 7}$$ or something of the sort. Is there an easier way?

## 2 Answers

We wish to solve the equation $$a + b + c_1 + c_2 + c_3 + c_4 + c_5 + c_6 + c_7 + c_8 = 100 \tag{1}$$ in the nonnegative integers subject to the constraints $a \leq 5$ and $b \geq 5$.

Since $b \geq 5$, $b' = b - 5$ is a nonnegative integer. Substituting $b' + 5$ for $b$ in equation 1 yields \begin{align*} a + b' + 5 + c_1 + c_2 + c_3 + c_4 + c_5 + c_6 + c_7 + c_8 & = 100\\ a + b' + c_1 + c_2 + c_3 + c_4 + c_5 + c_6 + c_7 + c_8 & = 95 \tag{2} \end{align*} Equation 2 is an equation in the nonnegative integers. A particular solution of equation 2 corresponds to the placement of nine addition signs in a row of $95$ ones. The number of solutions of equation 2 is $$\binom{95 + 9}{9} = \binom{104}{9}$$ since we must choose which $9$ of the $104$ positions needed for $95$ ones and $9$ addition signs will be filled with addition signs.

We have addressed the constraint $b \geq 5$, but we still have the constraint that $a \leq 5$. If this constraint is violated, then $a \geq 6$. Therefore, we must subtract the number of nonnegative integer solutions of equation 2 in which $a \geq 6$ from the number of solutions of equation 2.

Suppose $a \geq 6$. Then $a' = a - 6$ is a nonnegative integer. Substituting $a' + 6$ for $a$ in equation 2 yields \begin{align*} a' + 6 + b' + c_1 + c_2 + c_3 + c_4 + c_5 + c_6 + c_7 + c_8 & = 95\\ a' + b' + c_1 + c_2 + c_3 + c_4 + c_5 + c_6 + c_7 + c_8 & = 89 \tag{3} \end{align*} Equation 3 is an equation in the nonnegative integers with $$\binom{89 + 9}{9} = \binom{98}{9}$$ solutions.

Hence, the number of solutions of equation 1 that satisfy the constraints $a \leq 5$ and $b \geq 5$ is $$\binom{104}{9} - \binom{98}{9}$$

It is akin to putting $100$ identical balls in $10$ distinct bins

Put $5$ balls to start with in bin b, $95$ more remain to be put.

To count and exclude invalid solutions, put $6$ in bin a, with $89$ now left to be put any which way.

Thus, applying stars and bars, answer $= \dbinom{95+10-1}{10-1} - \dbinom{89+10-1}{10-1}$