2
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.