1
$\begingroup$

Find the number of solutions to : $$x_1 + x_2 + x_3 + x_4 + x_5 = 10$$ where none of the variables can be the number $3$.

I can solve this with Inclusion-Exclusion Principle, but I really love solving this kind of problem with generating functions. I did not manage to solve it with generating functions , this is my try:

I have $5$ variables. None of them can be the number $3$. Need to find : coefficient of $${x^{10}}$$ so:

  • $x_1$ can be : $0 , 1 , 2, 4 ,5 , 6, \ldots$ to infinity, that means:

$$1 + x + {x^2} + {x^4} + {x^5} + {x^6} + .....$$ and this is relevant for all of the five variables so thats means total: $${(1 + x + {x^2} + {x^4} + ...)^5}$$

but I can't find the generating function of this series. I tried to multiply the series by $x$ and then subtract the original series from the multiplied one $$\begin{array}{l}1 + x + {x^2} + {x^{{4^{}}}} + ...\\ - {\rm{ }}x + {x^2} + {x^3} + {x^4} + ...\end{array} $$ and I get: $${\left( {\frac{{1 - {x^3}}}{{1 - x}}} \right)^5} $$

but the final solution after I'm using binomial expansion is $1$, and that's not correct.

Can I get help please?

Thanks.

$\endgroup$
  • $\begingroup$ Is there some purpose for all the comments in the source? It is slightly inconvenient to see it flash by. $\endgroup$ – quid Jul 6 '15 at 10:08
  • $\begingroup$ so remove all my explanations ? I want it to be comfratble to read. I wrote what I tried for solving it. $\endgroup$ – idan di Jul 6 '15 at 10:11
  • 1
    $\begingroup$ Not the explanations! The lines starting with '%...' in the source! $\endgroup$ – martini Jul 6 '15 at 10:11
  • $\begingroup$ I mean as @martini said this stuff % MathType! MTEF!2!1!+- % feaagKart1ev2a aatCvAUfeBSjuyZL2yd9gzLb vyNv2Ca erbuLwBLn % hiov2DGi1 BTfMBaeXatL xBI9gBaerbd9wDYLwz YbItLDharqqtubsr % 4rNCHbGeaGqiV u0Je9sqqrpepC0xbb L8F4rqqrFfpeea0xe9 Lq-Jc9 $\endgroup$ – quid Jul 6 '15 at 10:12
  • $\begingroup$ this is how you seeing my messege ? $\endgroup$ – idan di Jul 6 '15 at 10:13
1
$\begingroup$

You can also use Inclusion–exclusion principle.

Without the restriction $x_i\neq 3$ you have $$\binom{10+5-1}{10}$$ solutions.

Now you need to check how many bad cases you have. Denote the set of all solutions with $x_i=3$ by $A_i$. Your bad cases are $$A_1\cup A_2\cup A_3\cup A_4\cup A_5.$$ Can you take it from here?

$\endgroup$
  • $\begingroup$ I'm trying to solve with this approach. so S0 = |u| = all the solution for this problem which is what you wrote . so now x1 have three balls for example then I've left with 0 0 0 0 0 0 0 (7) balls and 4 cells so -> 000 | | | | so this is D(4,7) and I have totall 5 like this so s1 = |A| +|B|+|C|+|D|+|E| = 5 * D(4,7) ? am I in the right direction ? $\endgroup$ – idan di Jul 6 '15 at 13:33
  • $\begingroup$ Yes, and now you need to compute $|A_i\cap A_j|$ and to notice that there are $\binom{5}{2}$ pairs. $\endgroup$ – Ofir Schnabel Jul 7 '15 at 8:23
  • $\begingroup$ yes. I solved it yestarday. thanks $\endgroup$ – idan di Jul 7 '15 at 17:18
1
$\begingroup$

You can express your close-to-geometric sum as the difference between sums, i.e.

$$f(x)=\sum_{k\ge 0} x^k -x^3=\frac{1}{1-x}-x^3=\frac{1-x^3+x^4}{1-x}$$

Then we have

$$F(x)=\left(\frac{1-x^3+x^4}{1-x}\right)^5=\sum_{j\ge0}\binom{j+4}{4}x^j\cdot\sum_{a+b+c=5}\binom{5}{a,b,c}(-1)^bx^{3b+4c}$$

and equating coefficients we have that $10=j+3b+4c\ \to j=10-3b-4c$ and $j,b,c\ge 0$ and $b+c\le 5\ \to c\le 5-b$. So

$$[x^{10}]F(x)=\sum_{b+c\le 5}\binom{14-3b-4c}{4}\binom{5}{5-b-c,b,c}(-1)^b$$

You can simplify this sum seeing that $14-3b-4c\ge 4$ and so on.

Alternatively you can take the $[x^{10}]$ coefficient from the Maclaurin series of $F(x)$ using some CAS.

$\endgroup$
0
$\begingroup$

Note that $$ \frac{1-x^3}{1-x} = 1+x+x^2 $$ so in $(1+x+x^2)^5$ you are counting only the solutions with $0 \le x_i \le 2$ of which there is in fact only one.

Note that $$ (1-x)\sum_{i\ne 3} x^i = \sum_{i\ne 3} x^i - \sum_{i\ne 0,4} x^i = 1 + x^4 - x^3 $$ So we are left with $$ \left(\frac{1 - x^3 + x^4}{1-x}\right)^5 $$ Now do your expansion again.


Addendum: We have, $$ (1-x^3+x^4)^5 = \sum_{i+j+k = 5} \frac{5!}{i!j!k!} (-1)^jx^{3j+4k} $$

$\endgroup$
  • $\begingroup$ I know to solve this $$\frac{1}{{{{(1 - x)}^5}}} = {(1 - x)^{ - 5}} % MathType!MTEF!2!1!+- % feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x % fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaWaaSaaaeaaca % aIXaaabaGaaiikaiaaigdacqGHsislcaWG4bGaaiykamaaCaaaleqa % baGaaGynaaaaaaGccqGH9aqpcaGGOaGaaGymaiabgkHiTiaadIhaca % GGPaWaaWbaaSqabeaacqGHsislcaaI1aaaaaaa!4292! $$ $\endgroup$ – idan di Jul 6 '15 at 10:21
  • $\begingroup$ but how to solve the trinomial $${(1 - x)^{ - 5}}*{(1 - {x^3} + {x^4})^5} % MathType!MTEF!2!1!+- % feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x % fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaaiikaiaaig % dacqGHsislcaWG4bGaaiykamaaCaaaleqabaGaeyOeI0IaaGynaaaa % kiaacQcacaGGOaGaaGymaiabgkHiTiaadIhadaahaaWcbeqaaiaaio % daaaGccqGHRaWkcaWG4bWaaWbaaSqabeaacaaI0aaaaOGaaiykamaa % CaaaleqabaGaaGynaaaaaaa!4537! $$ $\endgroup$ – idan di Jul 6 '15 at 10:23
  • $\begingroup$ Added somehing @idandi $\endgroup$ – martini Jul 6 '15 at 12:03
  • $\begingroup$ i+j+k = 5 means that whenever 1 = 0 so, j=1, k = 4 ? and vice versa ? I thought it will be simpler with generating functions. I guess its more practical solveing it with another method $\endgroup$ – idan di Jul 6 '15 at 12:59

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.