4
$\begingroup$

How many integer solutions are there to the equation $x_1 + x_2 + x_3 + x_4 = 12$ with $x_i > 0$ for each $i \in \{1, 2, 3, 4\}$? How many solutions with $x_1 > 1$, $x_2 > 1$, $x_3 > 3$, $x_4 \geq 0$?

So for the first part I did this:

We set $x_i = y_i + 1$ for $i = 1, 2, 3$ and obtain $y_1 + y_2 + y_3 = 12 − 3 = 9$.

So, there is one-to-one correspondence between the positive integer solutions of $x_1 + x_2 + x_3 = 12$ and the non-negative integer solutions of $y_1 + y_2 + y_3 = 9$.

Hence, both equation have the same number of solutions. Since $y_1 + y_2 + y_3 = 9$ has ${9+3-1 \choose 3-1} = {11 \choose 2} = 55$ integer solutions.

Is this correct?

For the second part I do not understand how to figure out how many solutions with $x_1 > 1$, $x_2 > 1$, $x_3 > 3$, $x_4 \geq 0$?

$\endgroup$
  • 1
    $\begingroup$ Your first part is correct. For second use a similar approach. Hint: $x_3=y_3+3$. $\endgroup$ – Anurag A Jan 27 '16 at 4:01
  • $\begingroup$ If you know generating functions, both excercises are easy $\endgroup$ – sinbadh Jan 27 '16 at 4:12
1
$\begingroup$

I am not sure why you have four variables in the statement of your question and three variables in your answer. I will assume you meant to work with four variables.

How many integer solutions are there to the equation $x_1 + x_2 + x_3 + x_4 = 12$ with $x_i > 0$ for each $i \in \{1, 2, 3, 4\}$?

We wish to solve the equation $$x_1 + x_2 + x_3 + x_4 = 12 \tag{1}$$ in the positive integers.

Method 1: We reduce the problem to one in the non-negative integers. Let $y_k = x_k - 1$ for $1 \leq k \leq 4$. Then each $y_k$ is a non-negative integer. Substituting $y_k + 1$ for $x_k$, $1 \leq k \leq 4$, in equation 1 yields \begin{align*} y_1 + 1 + y_2 + 1 + y_3 + 1 + y_4 + 1 & = 12\\ y_1 + y_2 + y_3 + y_4 & = 8 \tag{2} \end{align*} Equation 2 is an equation in the non-negative integers. A particular solution corresponds to placing three addition signs in a row of eight ones. For instance, $$1 1 1 1 1 + 1 + 1 1 1$$ corresponds to the solution $y_1 = 5$, $y_2 = 1$, and $y_3 = 3$, while $$1 1 + + 1 1 1 1 1 1$$ corresponds to the solution $y_1 = 2$, $y_2 = 0$, and $y_3 = 6$. Thus, the number of solutions of equation 2 is the number of ways three addition signs can be inserted into a row of eight ones, which is $$\binom{8 + 3}{3} = \binom{11}{3}$$ since we must choose which three of the eleven symbols (eight ones and three addition signs) will be addition signs.

Method 2: A particular solution of equation 1 in the positive integers corresponds to inserting three addition signs in the eleven spaces between successive ones in a row of $12$ ones. $$1 \square 1 \square 1 \square 1 \square 1 \square 1 \square 1 \square 1 \square 1 \square 1 \square 1 \square 1$$ For instance, $$1 1 1 + 1 1 1 1 + 1 1 1 1 1$$ corresponds to the solution $x_1 = 3$, $x_2 = 4$, and $x_3 = 5$. Thus, the number of solutions of equation 1 in the positive integers is the number of ways three addition signs can be inserted into the eleven gaps between successive ones in a row of $12$ ones, which is $$\binom{11}{3}$$

How many integer solutions are there to the equation $x_1 + x_2 + x_3 + x_4 = 12$ with $x_1 > 1$, $x_2 > 1$, $x_3 > 3$, $x_4 \geq 0$?

We reduce the problem to one in the non-negative integers. Since $x_1$ is an integer, $x_1 > 1 \implies x_1 \geq 2$. Similarly, since $x_2$ and $x_3$ are integers, $x_2 > 1 \implies x_2 \geq 2$ and $x_3 > 3 \implies x_3 \geq 4$. Let \begin{align*} y_1 & = x_1 - 2\\ y_2 & = x_2 - 2\\ y_3 & = x_3 - 4\\ y_4 & = x_4 \end{align*} Then each $y_k$, $1 \leq k \leq 4$, is a non-negative integer. Substituting $y_1 + 2$ for $x_1$, $y_2 + 2$ for $x_2$, $y_3 + 4$ for $x_3$, and $y_4$ for $x_4$ in equation 1 yields \begin{align*} y_1 + 2 + y_2 + 2 + y_3 + 4 + y_4 & = 12\\ y_1 + y_2 + y_3 + y_4 & = 4 \tag{3} \end{align*} Equation 3 is an equation in the non-negative integers with $$\binom{4 + 3}{3} = \binom{7}{3}$$ solutions.

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