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
    Commented Mar 6, 2015 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
    Commented Mar 7, 2015 at 14:45
  • $\begingroup$ i bet the principle of inclusion and exclusion is involved in the solution. why such a user name? $\endgroup$
    – abel
    Commented Mar 8, 2015 at 16:36

4 Answers 4

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$ Commented Mar 6, 2015 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
    Commented Mar 6, 2015 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
    Commented Mar 6, 2015 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
    Commented Mar 6, 2015 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$ Commented Mar 7, 2015 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$ Commented Mar 7, 2015 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
    Commented Mar 7, 2015 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$ Commented Mar 7, 2015 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
    Commented Mar 7, 2015 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
    Commented Mar 7, 2015 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
    Commented Mar 6, 2015 at 11:47
  • $\begingroup$ How did you count 126, 135, 144, 225....? $\endgroup$ Commented Mar 6, 2015 at 11:47
  • $\begingroup$ @Coffee What is the arrangement theorem? I googled but didnt find anything. $\endgroup$ Commented Mar 6, 2015 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
    Commented Mar 6, 2015 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$ Commented Mar 6, 2015 at 11:44
  • $\begingroup$ How does "This was an easy one . Try my trigonometry bash" contribute to the answer? $\endgroup$
    – JiK
    Commented Mar 6, 2015 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$ Commented Mar 6, 2015 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$ Commented Mar 6, 2015 at 14:44

Not the answer you're looking for? Browse other questions tagged .