Number of solutions to equation $x_1 + x_2 + \cdots + x_n = k $ under the constraint that each variable here is nonnegative.

Question

Number of solutions to equation $x_1 + x_2 + \cdots + x_n  = k $ under the constraint that each variable here is nonnegative.

parthkohli · Answer

I haven't studied this yet but I sorta want to figure out the answer to this on my own. Something that comes to mind is a recursive sequence/relation between $n,k$ and $n+1, k$ etc. Still thinking.

anonymous · Answer

Srry im just starting alg 1

parthkohli · Answer

We all start there.

parthkohli · Answer

@ganeshie8 any ideas?

ganeshie8 · Answer

This is stars and bars problem
Consider  $n+k$ stars and $n-1$ bars

ganeshie8 · Answer

Before generalizing, maybe lets work an example problem by giving specific numbers to $k$ and $n$

ganeshie8 · Answer

How about $n=5$ and $k=13$

Find the number of nonnegative integer solutions to the equation 
$a+b+c+d+e = 13$

parthkohli · Answer

Yes. Is the "stars-and-bars" idea better to work with and think about? I can see why they're the same problems though.

parthkohli · Answer

How do we work with this?

ganeshie8 · Answer

Yes, stars and bars is just a visualization technique

ganeshie8 · Answer

13 is kinda large,
lets try a much simpler example : 
$a+b+c+d+e = 7 $

ganeshie8 · Answer

Consider $7$ stars and $4$ bars : 

$\star |\star| \star \star| \star \star| \star $

parthkohli · Answer

Yes, a = 1, b = 1, c = 2, d = 2, e = 1

ganeshie8 · Answer

above arrangement represents a solution : 
$(1,1,2,2,1)$

ganeshie8 · Answer

right, what about below
$\star |\star| |\star \star \star \star| \star$

parthkohli · Answer

1, 1, 0, 4, 1

parthkohli · Answer

I see what it represents, but it doesn't get us any closer to solving the question though, right?

ganeshie8 · Answer

Notice that the problem translates to finding number of ways of "placing" the four bars between the seven stars

ganeshie8 · Answer

How many locations are there for placing 4 bars ?

parthkohli · Answer

That's what we have to figure out...

ganeshie8 · Answer

Isn't it trivial to figure that out just by looking at the stars and bars ?

ganeshie8 · Answer

$\star |\star| |\star \star \star \star| \star$

$7+4 = 11$ locations
you have $4$ bars
so total number of ways of placing $4$ bars in available $11$ locations is $\dbinom{11}{4}$

parthkohli · Answer

Ew...

ganeshie8 · Answer

lets do one more example problem

parthkohli · Answer

Wow, OK.

ganeshie8 · Answer

find number of nonnegative integer solutions to the equation
$a+b+c = 5$

ganeshie8 · Answer

you want to partition $5$ into $3$ parts

so consider $5$ stars and $2$ bars

parthkohli · Answer

Where did you come up with 7 + 4? Theoretically, I could place all the four bars to the left of all seven stars.

ganeshie8 · Answer

sure, you can, thats one solution : $(0,0,0,0,7)$

ganeshie8 · Answer

$||||\star \star \star \star \star \star \star$

Notice that the length of above string doesn't change, it is still $11$

parthkohli · Answer

Oh, so I had to look at it as a string! Nice.

parthkohli · Answer

Thanks!

ganeshie8 · Answer

if it helps, yeah.. 
it is a simple concept but many combinatorics problems keep refering to this concept..

ganeshie8 · Answer

what that knowledge of stars and bars, see if you can find the number of "positive" integer solutions to the equation
$a+b+c+d+e=7$

parthkohli · Answer

$$\large  \star | \star  \star| \star| \star \star | \star $$No. of ways of placing $4$ bars among $7$ stars = $\binom{11}{4}$
Each such case points to exactly one solution.
So ...

parthkohli · Answer

Am I missing something? Is that the number of nonnegative solutions too?

ganeshie8 · Answer

Nope. How is that different from the earlier problem of finding number of "nonnegative" integer solutions ?

parthkohli · Answer

Oh, you really meant positive. I just thought you placed the quotes around "positive" to mean nonnegative.

OK.

We subtract all cases where two or more bars are placed together.

ganeshie8 · Answer

$\large  \star | |\star  \star \star| \star \star | \star$

two adjacent bars is not allowed

parthkohli · Answer

If we consider two bars as a unit, we can safely say that the number of ways is $\binom{10}{3}$. If I subtract this from the original, we will also be subtracting those cases where 3 bars and 4 bars are placed together, if I'm not wrong.

parthkohli · Answer

So the number of positive solutions is $\binom{11}{4} - \binom{10}3$ ...?

ganeshie8 · Answer

that might work
we could also use the previous trick :
simply consider the number of locations for bars

ganeshie8 · Answer

$7$ stars :
$\star~~\star~~\star~~\star~~\star~~\star~~\star $

where can the $4$ bars go ?

parthkohli · Answer

oh nice! let me answer this

parthkohli · Answer

|dw:1442673808024:dw|