Question

Find the number of non negative integer solutions for x+y+z+b+c=8
x , y ,z ,b ,c > = 0

Answer 1

you may use stars and bars

Answer 2

i will try it out

Answer 3

stars and bars??

Answer 4

https://brilliant.org/discussions/thread/stars-and-bars/

Answer 5

what are stars and bars

Answer 6

\[x+y+z+b+c=8\]

you have \(5\) variables on left side and you want them add up to \(8\)

Answer 7

yeah

Answer 8

so you take \(8\) stars and \(5-1\) bars :

\[\large \star \star| \star \star| \star|\star \star| \star \]

Answer 9

How on earth is this related to the original problem of fining number of nonnegative integer solutions to \(x+y+z+b+c = 8\) ?

Answer 10

yes

Answer 11

How do i know , i am asking the question

Answer 12

Here is the trick :
the "number of stars" before the first bar is the value of \(x\),
the "number of stars" between first bar and the second bar is the value of \(y\) etc..

Answer 13

for example :

\[\large \star \star| \star \star| \star|\star \star| \star \]

refers to the solution

\(x=2\)
\(y=2\)
\(z=1\)
\(b=2\)
\(c=1\)

Answer 14

what is "x" and "y" and how do you divide them with bars ,

Answer 15

ok got it

Answer 16

but how do you divide themwith bars

Answer 17

lets do two more examples before working the final answer

Answer 18

we will see shortly, its easy :) find the solution corresponding to below stars and bars pattern :
\[\large \star |\star| \star \star \star|\star \star| \star\]

Answer 19

fine..

Answer 20

x=1 , y=1 , z =3 , b= 2 , c=1

Answer 21

You got it ! ok last example :
\[\large |\star \star| \star \star \star|\star \star| \star\]

Answer 22

x=0
y=2
z=3
b=2
c=1

Answer 23

Excellent! we're ready to solve the actual problem

Answer 24

cool

Answer 25

8+4 = 12
there are \(12\) places to choose from for the \(4\) bars. so the answer is simply :
\[\large ^{12}C_4\]

Answer 26

we're done!

Answer 27

wait 1 min

Answer 28

the answer is correct let me think

Answer 29

sure feel free to ask if anything doesnt make sense..
this method won't be obvious for the first couple of times...

Answer 30

how 12 places

Answer 31

well i didn't read the website

Answer 32

number of places = (number of stars) + (number of bars)

Answer 33

I am reading thanks for help, will tag you if i don't understand

Answer 34

number of stars = 8
number of bars = 5-1

Answer 35

don't go to that website.. it can be confusing..

Answer 36

I see you get the general idea. Just work couple more example problems and im sure you will get hang of it..

Answer 37

yes

Answer 38

total places = Number of stars + Number of bars

Answer 39

Here is an example problem that you may try

Find the number of nonnegative integer solutions of \(x+y+z = 5\)

Answer 40

7C2

Answer 41

it is correct right?

Answer 42

Yes! one more if you want :
\[a+b+c+d+e+f = 1213123\]

Answer 43

As you can see it wont take much effort to answer the problem once you see how it works using stars and bars

Answer 44

now it seems easy peasy thank you

Answer 45

Find the number of integral sollutions ?

Answer 46

If that was the question then?

Answer 47

yes find the number of nonnegative integer solutions

Answer 48

and what about the negative sollutions?

Answer 49

as it is asked integral sollutions

Answer 50

there will be infinitely many integer solutions so nobody usually asks that question

Answer 51

consider below equation
\[x-y = 1\]

every pair of integers \((t+1, t)\) satisfy the above equation yes ?

Answer 52

conditions must be different on variables for finite sollutions to exist , it didn't strike me

Answer 53

yes if the linear equation \(ax+by = c\) has an integral solution, then it will have infinitely many integral solutions.

Answer 54

equations like these are called "linear diophantine equations"