Question

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

Answer 1

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.

Answer 2

@ganeshie8

Answer 3

Hey you may use generating functions

Answer 4

Can you give a good place to learn that ? :/ my textbook has described it in a complicated way :|

Answer 5

I have a very good tutorial on generating functions, one sec

Answer 6

Here it is
http://db.math.ust.hk/notes_download/elementary/algebra/ae_A11.pdf

@DLS

Answer 7

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})\)

Answer 8

There are no restrictions on other four variables, so the corresponding factor for each of them is
\((x^0+x^1+x^2+\cdots)\)

Answer 9

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\]

Answer 10

The answer for part 1 is the coefficient of \(x^{21}\) of \(G(x)\)

Answer 11

Can you think of a way to find the coefficient of \(x^{21}\) of \(G(x)\) ?

Answer 12

oh this thing is called generating functions? :D didn't know that.
we can use multinomial theorem maybe?

Answer 13

we don't really need to get all that sophisticated

Answer 14

binomial theorem will do :)

Answer 15

how are you planning to apply binomial here :o

Answer 16

\[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 ?

Answer 17

\[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


\]

Answer 18

does that look okay to you?

Answer 19

I have just used the partial sum and infinite sum formulas of geometric series

Answer 20

what did you do in the first term :o

Answer 21

\[x^0+x^1+x^2+\cdots + x^{10}\]

Notice that this is a geometric series with first term = \(1\) and common ratio = \(x\)

Answer 22

remember the partial sum formula of geometric series ?

Answer 23

oh right! sorry,my bad, yeah got that step!

Answer 24

good, try simplifying that expression a bit

Answer 25

i can proceed now :)

Answer 26

familiar with extended binomial theorem for negative exponents ?

Answer 27

\[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}


\]

Answer 28

see if that looks okay

Answer 29

yep :)

Answer 30

we can open the bracket now i guess

Answer 31

\[=>(1-x^{11}) - x^{11}(1-x)^5\]

Answer 32

we could apply binomial theorem on the 2nd term :o

Answer 33

yeah that's fine too :)

Answer 34

\[=>(1-x^{11}) - x^{11}(1-x)^5\]

how did you get that ?

Answer 35

sorry the power is -5

Answer 36

\[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)


\]

Answer 37

I meant this..but it isn't required.
\[\Large (1-x^{-5}) - x^{11}(1-x^{-5})\]

Answer 38

I thought of writing it like that because the coefficient of x^17 would only come from the 2nd term.

Answer 39

do you mean
I meant this..but it isn't required.
\[\Large (1-x)^{-5} - x^{11}(1-x)^{-5}\]

?

Answer 40

yeah :P equation editor is trolling me today :/

Answer 41

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

Answer 42

whats the coefficient of \(x^{21}\) in the expansion of \((1-x)^{-5}\) ?

Answer 43

\[\large C(-5,r)1^r (-x)^{-n-r} => C(-5+r-1,r)(-x)^{-5-r}\]

Answer 44

-5-r = 21
r = -26?

Answer 45

This is the 2nd or 3rd time I happen to use binomial theorem for negative index :|

Answer 46

you're making it way more complicated than it actually is

Answer 47

lol sorry

Answer 48

whats the coefficient of \(x^{21}\) in the expansion of \((1-x)^{-5}\) ?

the term is : \(C(-5, 21) (-x)^{21}\)

Answer 49

therefore the coefficient of \(x^{21}\) is simply \(-C(-5, 21)\)

Answer 50

How we evaluate that is another story

Answer 51

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 :)

Answer 52

its all good :) see if you can find the "required" coefficient in second term

Answer 53

\[\Large (1-x)^{-5} - x^{11}\color{red}{(1-x)^{-5}}\]

Answer 54

do we need the coefficient of \(x^{10}\) in that red term ?

Answer 55

yep..we need all such indices which can add up with 11 to produce 21

Answer 56

there is only one number that produces 21 when added to 11

Answer 57

and that number is 10

Answer 58

once you see how all this works, it is a very simple problem actually...

Answer 59

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 ?

Answer 60

\((1-x)^{-5} = \sum\limits_{k-0}^{\infty}C(-5, k)(-x)^k\)

Answer 61

as you can see it will have all the powers of x

Answer 62

we're just looking for the coefficient of \(x^{21}\)

Answer 63

I don't know why I'm getting so much confused lol, I get it :D

Answer 64

its okay, read the first 3 pages of the pdf i gave you earlier

Answer 65

ALRIGHT! so we have the coefficient from the 2nd term now.

Answer 66

and the first term as well

Answer 67

just a last step to evaluate that term

Answer 68

what is the coefficient from second term ?

Answer 69

C(-5,10)

Answer 70

+C(-5,21) from the first term

Answer 71

= total answer

Answer 72

Excellent! careful about the signs though

Answer 73

oh yes. there is a (-1)^n hanging around there

Answer 74

only the first term should have it.

Answer 75

\[\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)\]

Answer 76

that is our final answer

Answer 77

yep!!

Answer 78

evaluate that

Answer 79

treat that same as a regular binomial coefficient

Answer 80

\[C(n,k) = \dfrac{n(n-1)(n-2)\cdots (n-k+1)}{k!}\]

Answer 81

\[C(-5,21) = \dfrac{-5(-5-1)(-5-2)\cdots (-5-21+1)}{21!}\]

Answer 82

whatever you get

Answer 83

it should simplify nicely though

Answer 84

lets try

Answer 85

\[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!}
\]

Answer 86

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)
\]

Answer 87

that is just a regular binomial coefficient which you can evaluate using ur calculator

Answer 88

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)\]

Answer 89

?

Answer 90

ohh..nice :D so did you generalize a formula for negative coefficient btw ?
\[\Large (-1)^r C(r-n+1)\]

Answer 91

Now I see... you have tried to use that formula earlier right ?

Answer 92

haha yes :p

Answer 93

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)
\]

Answer 94

does that look good ?

Answer 95

yeah alot better :D

Answer 96

wolfram says the final answer is 11649

http://www.wolframalpha.com/input/?i=-%28-5+choose+21%29-%28-5+choose+10%29

Answer 97

il let you finish it off :)