0
$\begingroup$

How many solutions does the equation $x_1 + x_2 + x_3$ = 11 have, where $x_1$ , $x_2$ and $x_3$ are nonnegative integers?

I was attempting to solve the problem by using the method of mutually exclusive cases ie setting $x_1$ to 1 and having $x_2$ 2 and ect but then online i see a lot of questions are utilizing the stars and bars method and I was wondering how to do that rather than just brute forcing the problem?

$\endgroup$
1
$\begingroup$

To solve the problem using mutually exclusive cases:

Notice that $x_1$ can assume each value between $0$ and $11$, inclusive.

If $x_1 = 0$, then $x_2 + x_3 = 11$. The equation $x_2 + x_3 = 11$ has $12$ solutions since $x_3 = 11 - x_2$ and $x_2$ can assume each of the $12$ values between $0$ and $11$, inclusive.

If $x_1 = 1$, then $x_2 + x_3 = 10$. The equation $x_2 + x_3 = 10$ has $11$ solutions since $x_3 = 10 - x_2$ and $x_2$ can assume each of the $11$ values between $0$ and $10$, inclusive.

More generally, if $x_1 = k$, $0 \leq k \leq 11$, then $x_2 + x_3 = 11 - k$. The number of solutions of the equation $x_2 + x_3 = 11 - k$ is $11 - k + 1 = 12 - k$ since $x_3 = 11 - k - x_2$ can assume each of the $12 - k$ values between $0$ and $11 - k$, inclusive.

Hence, the number of solutions of the equation $$x_1 + x_2 + x_3 = 11$$ in the nonnegative integers is $$\sum_{k = 0}^{11} (12 - k) = \sum_{j = 1}^{12} j = \frac{12 \cdot 13}{2} = 78$$

To solve the problem using combinations with repetition:

We wish to find the number of solutions of the equation
$$x_1 + x_2 + x_3 = 11$$ in the nonnegative integers. A particular solution corresponds to the placement of two addition signs in a row of eleven ones. For instance, $$1 1 1 1 + 1 1 + 1 1 1 1 1$$ corresponds to the solution $x_1 = 4$, $x_2 = 2$, $x_3 = 5$, while $$+ 1 1 1 + 1 1 1 1 1 1 1 1$$ corresponds to the solution $x_1 = 0$, $x_2 = 3$, $x_3 = 8$. Hence, the number of solutions of the equation in the nonnegative integers is the number of ways we can insert two addition signs in a row of eleven ones, which is $$\binom{11 + 2}{2} = \binom{13}{2} = 78$$ since we must choose which two of the $13$ positions (eleven ones and two addition signs) will be filled with addition signs.

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