4
$\begingroup$

How to calculate the number of solutions of the equation $x_1 + x_2 + x_3 = 9$ when $x_1$, $x_2$ and $x_3$ are integers which can only range from 1 to 6.

$\endgroup$
3
  • 3
    $\begingroup$ hint: generating function. $\endgroup$ – user117449 Mar 6 '15 at 10:43
  • $\begingroup$ I don't get why people keep adding answers which will only work for small numbers. To all the people who cast the upvotes, do you really think it's a good answer to count all solutions? $\endgroup$ – AvZ Mar 7 '15 at 14:45
  • $\begingroup$ i bet the principle of inclusion and exclusion is involved in the solution. why such a user name? $\endgroup$ – abel Mar 8 '15 at 16:36
6
$\begingroup$

We can find the number of solutions using binomial theorem.
The coefficient of $x^9$ in the following will be the required answer. $$(x+x^2+\cdots+x^6)^3$$ This above, is a Geometric Progression. Therefore, $$=\left (\frac{x-x^7}{1-x}\right )^3$$ $$=(x-x^7)^3(1-x)^{-3}$$ Now apply binomial theorem to get the coefficient of $x^9$ $$\left (\binom{3}{0}x^3-\binom{3}{1}x^9+\binom{3}{2}x^{15}-\binom{3}{3}x^{21} \right )\left (\binom{2}{0}+\binom{3}{1}x+\binom{4}{2}x^2+\cdots\infty\right )$$ We can neglect all terms with exponent $>9$ $$\left (\binom{3}{0}x^3-\binom{3}{1}x^9\right )\left (\binom{2}{0}+\binom{3}{1}x+\binom{4}{2}x^2+\cdots+\binom{11}{9}x^9\right )$$ We get the the coefficeient of $x^9$ as $$\binom{3}{0}\binom{8}{6}-\binom{3}{1}\binom{2}{0}$$ $$=28-3$$ $$=25$$

$\endgroup$
10
  • $\begingroup$ Thanks for answering but can you please explain how you got $(x+x^2+\cdots+x^6)^3$. $\endgroup$ – Stupid Man Mar 6 '15 at 12:07
  • 1
    $\begingroup$ @StupidMan We have to find how many ways can we get $9$ from sum of each variable. $(x+x^2+\cdots+x^6)^3= (x+x^2+\cdots+x^6) (x+x^2+\cdots+x^6) (x+x^2+\cdots+x^6)$ This accounts for each variable with the value $1\leq x_1,x_2,x_3 \leq 6$. $\endgroup$ – AvZ Mar 6 '15 at 12:12
  • 1
    $\begingroup$ Note that if we get $x^9$, all the exponents will add up to $9$. Denoting all the possible ways to get $9$ with given restrictions. For example, if you wanted only even solutions, you would have something like this $(x^2+x^4+x^6)^3$ $\endgroup$ – AvZ Mar 6 '15 at 12:14
  • 1
    $\begingroup$ In $(x+x^2+\cdots+x^6)$, the exponent of $x$ accounts for all the possible values of a variable. Since all the variables are identical, we get $(x+x^2+\cdots+x^6)^3$. The coefficient of $x^9$ in the expansion of this will give us all the possible ways the exponent of $x$ can add up to $9$. $\endgroup$ – AvZ Mar 6 '15 at 12:22
  • $\begingroup$ Can you also explain how you got the second part of the product $\left (\binom{3}{0}-\binom{3}{1}x^6+\binom{3}{2}x^{12}-\binom{3}{3}x^{18} \right )\left (\binom{2}{0}+\binom{3}{1}x+\binom{4}{2}x^2+\cdots\infty\right )$? I read the binomial theorem for negative exponents here bsunewtonproject.wikispaces.com/file/view/Newton+project.pdf (only 100 kb file) but I still dont understand that part of your solution. $\endgroup$ – Stupid Man Mar 7 '15 at 14:34
5
$\begingroup$

Write $x_i = y_i + 1$, where $0\le y_1 \le 5$

Then you have:

$$y_1 + y_2 + y_3 = 6$$

And according to stars and bars we have: $$\binom{6+3-1}{6} = 28 \text{ combinations}$$

Now just exclude the $(6,0,0), (0,6,0)$ and $(0,0,6)$ and you have $25$ solutions


UPDATE:

Now to find all the solutions we should exclude let $y_1 = 6 + z_1$, where $z_1 \ge 0$, then you have: $z_1 + y_2 + y_3 = 0$, and according to stars and bars we have:

$$\binom{0+3-1}{0} = 1 \text{ solution}$$

Now since we have three varaibles we have $3\cdot 1$ solution to exclude.

Note working with bigger numbers you'll exclude some solutions twice. To add them again let $y_1=6+z_1$ and $y_2=6+z_2$ and you'll have:

$$z_1 + z_2 + y_3 = -6$$

which obviously doesn't yield any solution. Now since we have $\binom{3}{2} = 3$ such pairs we need to add $3 \cdot 0 = 0$ solutions. Also you need to exclude the solution when $y_1 = 6+z_1; y_2 = 6+z_2; y_3=6+z_3$, which gives you:

$$z_1 + z_2 + z_3 = -12$$

obviously this doesn't yield any solutions, so we need to exclude $\binom{3}{3} \cdot 0 = 0$ solutions.

$\endgroup$
15
  • $\begingroup$ How did you count (6, 0, 0), (0, 6, 0) and (0, 0, 6)? $\endgroup$ – Stupid Man Mar 7 '15 at 14:37
  • $\begingroup$ This is a bad approach IMHO. You're literally counting all the answers which will not fit. I bet you wouldn't even try this if I gave you $x_1+x_2+x_3=1000$ and $0\leq x_1,x_2,x_3\leq 750$ $\endgroup$ – AvZ Mar 7 '15 at 14:51
  • $\begingroup$ I have not explicitly mentioned in my question that the solution must work for larger cases also. @AvZ Your approach is great and I understand that it's a general method that can be used for other similar questions but the solution posted here does answer my question so I upvoted it. $\endgroup$ – Stupid Man Mar 7 '15 at 14:55
  • 1
    $\begingroup$ @StupidMan Since you are studying this. Odds are that questions with a bit larger numbers might appear in your examination/test/et cetera and counting all the solutions which don't fit would not really be a practical approach at all. Besides, almost all the other answers seem to be doing about the same. $\endgroup$ – AvZ Mar 7 '15 at 14:57
  • $\begingroup$ @AvZ It seems like you are trying to advertise your answer. I know that generating functions are a powerful tool, but somethimes they get messy and you need some calculation. Anyway do you know that counting combinations/permutations/variations using generating functions uses the include/exclude principle? This is pretty much the same, I will post an update just in second. $\endgroup$ – Stefan4024 Mar 7 '15 at 15:58
1
$\begingroup$

There are six situations. 126,135,144,225,234 and 333,it's easy to know there is no other situation. So,we can add each of them together using permutation theorem. $$P_3^3+P_3^3+\frac{P_3^3}{P_2^2}+\frac{P_3^3}{P_2^2}+P_3^3+\frac{P_3^3}{P_3^3}=25$$

$\endgroup$
3
  • $\begingroup$ what is "A" in this answer? $\endgroup$ – ASB Mar 6 '15 at 11:47
  • $\begingroup$ How did you count 126, 135, 144, 225....? $\endgroup$ – Stupid Man Mar 6 '15 at 11:47
  • $\begingroup$ @Coffee What is the arrangement theorem? I googled but didnt find anything. $\endgroup$ – Stupid Man Mar 6 '15 at 11:59
1
$\begingroup$

A very simple way first count no.of Positive solutions by $(n-1)C(r-1)$. I hope you understand the meaning of $C$.Then if $x_1$ is $7$ then no. of solutions is $1$ similarly for $x_2$ & $x_3$ is also $1$, so number of solution is $28-3=25$.

$\endgroup$
5
  • $\begingroup$ This is too ad hoc. What if we are dealing with larger numbers? $\endgroup$ – AvZ Mar 6 '15 at 11:23
  • $\begingroup$ Simply use the formula n-1Cr-1 and then find solutions by assuming variables out of the range and subtract from the original solution $\endgroup$ – Mayank Jha Mar 6 '15 at 11:44
  • $\begingroup$ How does "This was an easy one . Try my trigonometry bash" contribute to the answer? $\endgroup$ – JiK Mar 6 '15 at 11:53
  • $\begingroup$ I wanted to say that I have posted a question on trigonometry and want you to try it and give me a solution $\endgroup$ – Mayank Jha Mar 6 '15 at 11:58
  • $\begingroup$ I removed the irrelevant parts of your answer. Please see this tutorial on how to format mathematics on this site. $\endgroup$ – N. F. Taussig Mar 6 '15 at 14:44

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.