1
$\begingroup$

I am having some trouble with finding the number of integral solutions of an equation with a constraint given. I understand how go about solving without a constraint, but I don't know how to solve it when a constraint is given. Here's an example problem:

Find out how many solutions there are to the equation $y_1 + y_2 + y_3 + y_4 = 55$, satisfying the condition that each $y_i$ is a positive integer greater than 7?

I know if there wasn't a constraint, we'd just use the $\binom{r + n - 1}{r}$ formula and do $\binom{55+4-1}{55}$, but I have no idea what to do about the constraints. Any help?

$\endgroup$
4
  • $\begingroup$ Please check the statement of the question to make sure it is correct. The answer you gave does not correspond to the question you stated. $\endgroup$ – N. F. Taussig Apr 10 '16 at 3:39
  • $\begingroup$ @N.F.Taussig Thanks for pointing that out, I accidentally gave the answer to the wrong question. This question doesn't have an answer to it $\endgroup$ – user2896120 Apr 10 '16 at 3:41
  • $\begingroup$ The formula you give w/o constraints should be $\binom{55+4-1}{55}$ $\endgroup$ – true blue anil Apr 10 '16 at 3:46
  • $\begingroup$ @trueblueanil Just updated it, thanks for pointing that out! $\endgroup$ – user2896120 Apr 10 '16 at 3:48
2
$\begingroup$

Since $y_k$ is a positive integer greater than $7$, then $z_k = y_k - 8$ is a non-negative integer. If we make the substitution $z_k + 8$ for $y_k$, $1 \leq k \leq 4$, we obtain \begin{align*} y_1 + y_2 + y_3 + y_4 & = 55 \tag{1}\\ z_1 + 8 + z_2 + 8 + z_3 + 8 + z_4 + 8 & = 55\\ z_1 + z_2 + z_3 + z_4 & = 23 \tag{2} \end{align*} Equation 2 is an equation with the same number of solutions in the non-negative integers as equation 1 has in the positive integers larger than $7$. A particular solution of equation 2 corresponds to the placement of three addition signs in a row of $23$ ones. For instance, $$1 1 1 1 1 1 1 + 1 1 1 1 1 1 1 1 1 1 + + 1 1 1 1 1 1$$ corresponds to the solution $z_1 = 7$, $z_2 = 10$, $z_3 = 0$, and $z_4 = 6$. The number of solutions of equation 2 is equal to the number of ways three addition signs can be placed in a row of $23$ ones, which is $$\binom{23 + 3}{3} = \binom{26}{3}$$ since we must select which three of the twenty-six symbols (twenty-three ones and three addition signs) are addition signs.

$\endgroup$
2
  • $\begingroup$ Shouldn't it be $\binom{23 + 3}{23} = \binom{26}{23}$? $\endgroup$ – user2896120 Apr 11 '16 at 0:16
  • 1
    $\begingroup$ Observe that $$\binom{23 + 3}{23} = \binom{26}{23} = \frac{26!}{3!23!} = \frac{26!}{23!3!} = \binom{26}{3} = \binom{23 + 3}{3}$$ In general, $$\binom{n}{k} = \binom{n}{n - k}$$ because the number of ways of selecting $k$ of $n$ objects is equal to the number of ways of not selecting the remaining $n - k$ objects. $\endgroup$ – N. F. Taussig Apr 11 '16 at 1:31
1
$\begingroup$

Define $x_j = y_j - 7,$ and count the number of ways for the $x$s to add to $55-28 = 27$

Note: the other answers prefer subtracting $8$ so as to get $x_j \geq 0,$ sum $55-32 = 23.$ Well, why not?

$\endgroup$
0
$\begingroup$

A simple way is to pre-allot $8$ to each $y_i$,
so now the problem reduces to $y_1+y_2+y_3+y_4 = 23$, over non-negative integers

You already know what to do now.

$\endgroup$
0

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.