2
$\begingroup$

I'm reviewing for my final coming up and I'm not sure about my solution to this problem.

Find the number of integer solutions to $$x_1+x_2+x_3+x_4= 30$$ where $0\leq x_n <10$ for $1\leq n \leq 4$.

My first thought was to find the number of solutions where at least one of the x's is greater than ten and subtracting that from the total, which is equivalent to finding the number of integer solutions to

Find the number of integer solutions to $$x_1+x_2+x_3+x_4= 20.$$

That's a problem I know how to solve, and the answer is $nCr(23,20)=1771$.

Since there are $nCr(33,30)=5456$ total solutions, the final answer is $$5456-1771=3685.$$

Is this right?

$\endgroup$
  • 1
    $\begingroup$ No, that is no the number of solutions in which at least one $x$ is greater than $10$. $\endgroup$ – Jorge Fernández Hidalgo Dec 10 '15 at 17:25
  • 1
    $\begingroup$ You could use inclusion-exclusion, or alternatively, what you want is the coefficient of $x^{30}$ in $(\frac{x^{11}-1}{x-1})^4$ $\endgroup$ – Jorge Fernández Hidalgo Dec 10 '15 at 17:27
  • 1
    $\begingroup$ @dREaM: Minor typo, it should be $\left(\frac{x^{10}-1}{x-1}\right )^ 4$, great idea nevertheless! $\endgroup$ – Orest Bucicovschi Dec 10 '15 at 18:32
  • $\begingroup$ Oh yeah, for some reason I thought $x_n\leq 10$. Good eye! $\endgroup$ – Jorge Fernández Hidalgo Dec 10 '15 at 19:26
  • 2
    $\begingroup$ Possible duplicate of Enumerating number of solutions to an equation $\endgroup$ – user2838619 Dec 11 '15 at 18:55
3
$\begingroup$

$$|s|=\binom{30+4-1}{4-1}=\binom{33}{3}=\binom{33}{3}\\ A :x_1 \geq10 \to (x_1-10)+x_2+x_3+x_4=30-10 \to |A|=\binom{20+4-1}{4-1}=\binom{23}{3}\\ B::x_2 \geq10 \to x_1+(x_2-10)+x_3+x_4=30-10 \to |B|=\binom{23}{3}\\ C::x_3 \geq10 \to x_1+x_2+(x_3-10)+x_4=30-10 \to |C|=\binom{23}{3}\\ C::x_4 \geq10 \to x_1+x_2+x_3+(x_4-10)=30-10 \to |D|=\binom{23}{3}\\ A\cap B:x_1 \geq 10 ,x_2 \geq 10 \to (x_1-10)+(x_2-10)+x_3+x_4=30-10-10 \to |A\cap B|=\binom{10+4-1}{4-1}=\binom{13}{3}\\ ... |A\cap C|=|A\cap D|=|B\cap C|=|B\cap D|=|C\cap D|=\binom{13}{3}\\ A \cap B\cap C:x_1,x_2,x_3 \geq10 \to (x_1-10)+(x_2-10)+(x_3-10)+x_4=30-30 \\ \to |A \cap B\cap C|=\binom{0+4-1}{4-1}=1\\|A \cap B\cap D|=|B \cap C\cap D|=|A \cap C\cap D|=\binom{3}{3}=1\\ A \cap B\cap C\cap D:x_1,x_2,x_3,x-4 \geq10 \to (x_1-10)+(x_2-10)+(x_3-10)+(x_4-10)=30-40 \to |A \cap B\cap C\cap D|=0 \\ $$now answer is $$\\{\color{Red}{|s|-|A\cup B\cup C\cup D|=\\|s|-((|A|+|B|+|C|+|D|)-(|A \cap B|+...)+(|A \cap B \cap C|+...)-(|A \cap B\cap C\cap D|))=\\ \binom{33}{3}-(4\binom{23}{3}-6\binom{13}{3}+4\binom{3}{3}-0)} } $$

$\endgroup$
1
$\begingroup$

HINT:

I got $$ (x^9+x^8+x^7+x^6+x^5+x^4+x^3+x^2+x+1)^4 = \\ x^{36}+4 x^{35}+10 x^{34}+20 x^{33}+35 x^{32}+56 x^{31}+84 x^{30}+120 x^{29}+165 x^{28}+220 x^{27}+282 x^{26}+348 x^{25}+415 x^{24}+480 x^{23}+540 x^{22}+592 x^{21}+633 x^{20}+660 x^{19}+670 x^{18}+660 x^{17}+633 x^{16}+592 x^{15}+540 x^{14}+480 x^{13}+415 x^{12}+348 x^{11}+282 x^{10}+220 x^9+165 x^8+120 x^7+84 x^6+56 x^5+35 x^4+20 x^3+10 x^2+4 x+1$$

( cf. hint of @dREaM: ) so the number is $84$.

$\endgroup$
  • $\begingroup$ Interesting approach. How does it work, and why did you choose x^6? $\endgroup$ – Zachary F Dec 10 '15 at 18:32
  • $\begingroup$ @ZacharyF: In fact it's the coefficient of $x^{30}$ that matters ( due to symmetry it equals the one of $x^6$ ), since it $\endgroup$ – Orest Bucicovschi Dec 10 '15 at 18:34
0
$\begingroup$

It is correct. Answer is indeed correct $nCr(33,3)=nCr(30,30)=5456$ . Here application of multinomial theorem is done , for solution to $x_1 + x_2 +x_3 +.....+ x_r = n$, there are $(n+r-1)C(r-1)$ [ which is also the number of terms in multinomial sum, is equal to the number of monomials of degree n on the variables $x_1, …, x_m$ and here n=30 , r=4 so we get the total possible solution as $nCr(33,3)=nCr(30,30)=5456$

$\endgroup$
  • $\begingroup$ Are you sure this is right? Does it take into account $0 \leq x_n \leq 10$? $\endgroup$ – Colm Bhandal Dec 10 '15 at 17:45

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.