DLS
  • DLS
Find the number of solutions to the equation : x1+x2+x3+x4+x5 = 21 where xi is a non negative integer Provided that 1) 0<=x1<=10 2) x1 is from 0 to 3 , x2 is from 1 to 4, x3 >=15
Mathematics
  • Stacey Warren - Expert brainly.com
Hey! We 've verified this expert answer for you, click below to unlock the details :)
SOLVED
At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus. Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.
katieb
  • katieb
I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!
DLS
  • DLS
I know that the standard formula for calculating the number of non negative integral solutions is given by \(\Large C(n+r-1,r-1)\). And I know if there are constraints like \(\Large x_i > \alpha\) then we replace \(\Large x_i\) with \(\Large x_i - \alpha\) .(Hopefully I have these facts right). But I am not sure how to deal with these 2 conditions.
DLS
  • DLS
@ganeshie8
ganeshie8
  • ganeshie8
Hey you may use generating functions

Looking for something else?

Not the answer you are looking for? Search for more explanations.

More answers

DLS
  • DLS
Can you give a good place to learn that ? :/ my textbook has described it in a complicated way :|
ganeshie8
  • ganeshie8
I have a very good tutorial on generating functions, one sec
ganeshie8
  • ganeshie8
Here it is http://db.math.ust.hk/notes_download/elementary/algebra/ae_A11.pdf @DLS
ganeshie8
  • ganeshie8
1) 0<=x1<=10 you may proceed like this : since \(x_1\) can take values from \(0\) to \(10\), it can be 0 or 1 or 2 or .... or 10 the corresponding factor for \(x_1\) in the generating function is \((x^0+x^1+x^2+\cdots + x^{10})\)
ganeshie8
  • ganeshie8
There are no restrictions on other four variables, so the corresponding factor for each of them is \((x^0+x^1+x^2+\cdots)\)
ganeshie8
  • ganeshie8
The overall generating function is then given by \[G(x)= (x^0+x^1+x^2+\cdots + x^{10}) (x^0+x^1+x^2+\cdots )^4\]
ganeshie8
  • ganeshie8
The answer for part 1 is the coefficient of \(x^{21}\) of \(G(x)\)
ganeshie8
  • ganeshie8
Can you think of a way to find the coefficient of \(x^{21}\) of \(G(x)\) ?
DLS
  • DLS
oh this thing is called generating functions? :D didn't know that. we can use multinomial theorem maybe?
ganeshie8
  • ganeshie8
we don't really need to get all that sophisticated
ganeshie8
  • ganeshie8
binomial theorem will do :)
DLS
  • DLS
how are you planning to apply binomial here :o
ganeshie8
  • ganeshie8
\[G(x)= (x^0+x^1+x^2+\cdots + x^{10}) (x^0+x^1+x^2+\cdots )^4\] How are you planning to avoid binomial theorem here ?
ganeshie8
  • ganeshie8
\[G(x)= (x^0+x^1+x^2+\cdots + x^{10}) (x^0+x^1+x^2+\cdots )^4\\~\\ =(\dfrac{1-x^{11}}{1-x}) (\dfrac{1}{1-x})^4 \]
ganeshie8
  • ganeshie8
does that look okay to you?
ganeshie8
  • ganeshie8
I have just used the partial sum and infinite sum formulas of geometric series
DLS
  • DLS
what did you do in the first term :o
ganeshie8
  • ganeshie8
\[x^0+x^1+x^2+\cdots + x^{10}\] Notice that this is a geometric series with first term = \(1\) and common ratio = \(x\)
ganeshie8
  • ganeshie8
remember the partial sum formula of geometric series ?
DLS
  • DLS
oh right! sorry,my bad, yeah got that step!
ganeshie8
  • ganeshie8
good, try simplifying that expression a bit
DLS
  • DLS
i can proceed now :)
ganeshie8
  • ganeshie8
familiar with extended binomial theorem for negative exponents ?
ganeshie8
  • ganeshie8
\[G(x)= (x^0+x^1+x^2+\cdots + x^{10}) (x^0+x^1+x^2+\cdots )^4\\~\\ =(\dfrac{1-x^{11}}{1-x}) (\dfrac{1}{1-x})^4\\~\\ = (1-x^{11})(1-x)^{-5} \]
ganeshie8
  • ganeshie8
see if that looks okay
DLS
  • DLS
yep :)
DLS
  • DLS
we can open the bracket now i guess
DLS
  • DLS
\[=>(1-x^{11}) - x^{11}(1-x)^5\]
DLS
  • DLS
we could apply binomial theorem on the 2nd term :o
DLS
  • DLS
yeah that's fine too :)
ganeshie8
  • ganeshie8
\[=>(1-x^{11}) - x^{11}(1-x)^5\] how did you get that ?
DLS
  • DLS
sorry the power is -5
ganeshie8
  • ganeshie8
\[G(x)= (x^0+x^1+x^2+\cdots + x^{10}) (x^0+x^1+x^2+\cdots )^4\\~\\ =(\dfrac{1-x^{11}}{1-x}) (\dfrac{1}{1-x})^4\\~\\ = (1-x^{11})(1-x)^{-5}\\~\\ =(1-x^{11} )(\sum\limits_{k=0}^{\infty}\dbinom{-5}{k} (-x)^k) \]
DLS
  • DLS
I meant this..but it isn't required. \[\Large (1-x^{-5}) - x^{11}(1-x^{-5})\]
DLS
  • DLS
I thought of writing it like that because the coefficient of x^17 would only come from the 2nd term.
ganeshie8
  • ganeshie8
do you mean I meant this..but it isn't required. \[\Large (1-x)^{-5} - x^{11}(1-x)^{-5}\] ?
DLS
  • DLS
yeah :P equation editor is trolling me today :/
ganeshie8
  • ganeshie8
that looks god as you can see the first term \((1-x)^{-5}\) contains an \(x^{21}\) term and the second term \(x^{11}(1-x)^{-5}\) also contains an \(x^{21}\) term we need to find them both
ganeshie8
  • ganeshie8
whats the coefficient of \(x^{21}\) in the expansion of \((1-x)^{-5}\) ?
DLS
  • DLS
\[\large C(-5,r)1^r (-x)^{-n-r} => C(-5+r-1,r)(-x)^{-5-r}\]
DLS
  • DLS
-5-r = 21 r = -26?
DLS
  • DLS
This is the 2nd or 3rd time I happen to use binomial theorem for negative index :|
ganeshie8
  • ganeshie8
you're making it way more complicated than it actually is
DLS
  • DLS
lol sorry
ganeshie8
  • ganeshie8
whats the coefficient of \(x^{21}\) in the expansion of \((1-x)^{-5}\) ? the term is : \(C(-5, 21) (-x)^{21}\)
ganeshie8
  • ganeshie8
therefore the coefficient of \(x^{21}\) is simply \(-C(-5, 21)\)
ganeshie8
  • ganeshie8
How we evaluate that is another story
DLS
  • DLS
ohh..all this is because I haven't got the grip of this topic anymore :/ I had done it in XIIth or so, due to the gap in first year I have totally forgotten it :/ sorry..but I happen to remember it now :)
ganeshie8
  • ganeshie8
its all good :) see if you can find the "required" coefficient in second term
ganeshie8
  • ganeshie8
\[\Large (1-x)^{-5} - x^{11}\color{red}{(1-x)^{-5}}\]
ganeshie8
  • ganeshie8
do we need the coefficient of \(x^{10}\) in that red term ?
DLS
  • DLS
yep..we need all such indices which can add up with 11 to produce 21
ganeshie8
  • ganeshie8
there is only one number that produces 21 when added to 11
ganeshie8
  • ganeshie8
and that number is 10
ganeshie8
  • ganeshie8
once you see how all this works, it is a very simple problem actually...
DLS
  • DLS
yeah hopefully this would help in clearing alot of questions :| anyway, how do we get to know which all powers will (1-x)^-5 have ?
ganeshie8
  • ganeshie8
\((1-x)^{-5} = \sum\limits_{k-0}^{\infty}C(-5, k)(-x)^k\)
ganeshie8
  • ganeshie8
as you can see it will have all the powers of x
ganeshie8
  • ganeshie8
we're just looking for the coefficient of \(x^{21}\)
DLS
  • DLS
I don't know why I'm getting so much confused lol, I get it :D
ganeshie8
  • ganeshie8
its okay, read the first 3 pages of the pdf i gave you earlier
DLS
  • DLS
ALRIGHT! so we have the coefficient from the 2nd term now.
DLS
  • DLS
and the first term as well
DLS
  • DLS
just a last step to evaluate that term
ganeshie8
  • ganeshie8
what is the coefficient from second term ?
DLS
  • DLS
C(-5,10)
DLS
  • DLS
+C(-5,21) from the first term
DLS
  • DLS
= total answer
ganeshie8
  • ganeshie8
Excellent! careful about the signs though
DLS
  • DLS
oh yes. there is a (-1)^n hanging around there
DLS
  • DLS
only the first term should have it.
ganeshie8
  • ganeshie8
\[\Large (1-x)^{-5} - x^{11}\color{red}{(1-x)^{-5}}\] \(x^{21}\) coefficient from first term is \(-C(-5,21)\) \(x^{21}\) coefficient from second term is \(C(-5,10)\) subtract them to get \[-C(-5,21)-C(-5,10)\]
ganeshie8
  • ganeshie8
that is our final answer
DLS
  • DLS
yep!!
ganeshie8
  • ganeshie8
evaluate that
ganeshie8
  • ganeshie8
treat that same as a regular binomial coefficient
ganeshie8
  • ganeshie8
\[C(n,k) = \dfrac{n(n-1)(n-2)\cdots (n-k+1)}{k!}\]
ganeshie8
  • ganeshie8
\[C(-5,21) = \dfrac{-5(-5-1)(-5-2)\cdots (-5-21+1)}{21!}\]
ganeshie8
  • ganeshie8
whatever you get
ganeshie8
  • ganeshie8
it should simplify nicely though
ganeshie8
  • ganeshie8
lets try
ganeshie8
  • ganeshie8
\[C(-5,21) = \dfrac{-5(-5-1)(-5-2)\cdots (-5-21+1)}{21!}\\~\\ =\dfrac{(-1)^{21}5(5+1)(5+2)\cdots (5+21-1)}{21!} \]
ganeshie8
  • ganeshie8
Oh my! that is same as \[C(-5,21) = \dfrac{-5(-5-1)(-5-2)\cdots (-5-21+1)}{21!}\\~\\ =\dfrac{(-1)^{21}5(5+1)(5+2)\cdots (5+21-1)}{21!}\\~\\ =(-1)^{21}C(5+21-1,~21) \]
ganeshie8
  • ganeshie8
that is just a regular binomial coefficient which you can evaluate using ur calculator
ganeshie8
  • ganeshie8
That is so awesome! In general do we have below formula to convert negative binomial coefficients to positive : \[C(-n,~r) = (-1)^r C(n+r-1~r)\]
ganeshie8
  • ganeshie8
?
DLS
  • DLS
ohh..nice :D so did you generalize a formula for negative coefficient btw ? \[\Large (-1)^r C(r-n+1)\]
ganeshie8
  • ganeshie8
Now I see... you have tried to use that formula earlier right ?
DLS
  • DLS
haha yes :p
ganeshie8
  • ganeshie8
Oh my! that is same as \[C(-5,21) = \dfrac{-5(-5-1)(-5-2)\cdots (-5-21+1)}{21!}\\~\\ =\dfrac{(-1)^{21}5(5+1)(5+2)\cdots (5+21-1)}{21!}\\~\\ =(-1)^{21}C(5+21-1,~21)\\~\\ =-C(25,~21) \]
ganeshie8
  • ganeshie8
does that look good ?
DLS
  • DLS
yeah alot better :D
ganeshie8
  • ganeshie8
wolfram says the final answer is 11649 http://www.wolframalpha.com/input/?i=-%28-5+choose+21%29-%28-5+choose+10%29
ganeshie8
  • ganeshie8
il let you finish it off :)
DLS
  • DLS
yeah I can do the rest ! :D
DLS
  • DLS
I can probably do the 2nd part of the question too.
ganeshie8
  • ganeshie8
can you show me the generating function for part2 quick
ganeshie8
  • ganeshie8
im going for dinner... and i may not login again tonight
ganeshie8
  • ganeshie8
just want to see what you get for part2
DLS
  • DLS
2) x1 is from 0 to 3 , x2 is from 1 to 4, x3 >=15 \[\large (x^0+x^1+x^2+x^3)(x^1+x^2+x^3+x^4)(x^{15}+x^{16}...)\]
DLS
  • DLS
and rest two are infinite GP ..can be whatever
DLS
  • DLS
i.e 0 to infinity..so 2 more brackets multiplied by that
ganeshie8
  • ganeshie8
Excellent! Looks you have nailed these... gtg.. have fun :)
DLS
  • DLS
BIG THANKS TO YOU!! thanks for your precious time :")

Looking for something else?

Not the answer you are looking for? Search for more explanations.