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

- ParthKohli

- Stacey Warren - Expert brainly.com

Hey! We 've verified this expert answer for you, click below to unlock the details :)

- katieb

I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!

- ParthKohli

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

Srry im just starting alg 1

- ParthKohli

We all start there.

Looking for something else?

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

## More answers

- ParthKohli

@ganeshie8 any ideas?

- ganeshie8

This is stars and bars problem
Consider \(n+k\) stars and \(n-1\) bars

- ganeshie8

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

- ganeshie8

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

- ParthKohli

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

How do we work with this?

- ganeshie8

Yes, stars and bars is just a visualization technique

- ganeshie8

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

- ganeshie8

Consider \(7\) stars and \(4\) bars :
\(\star |\star| \star \star| \star \star| \star \)

- ParthKohli

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

- ganeshie8

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

- ganeshie8

right, what about below
\(\star |\star| |\star \star \star \star| \star\)

- ParthKohli

1, 1, 0, 4, 1

- ParthKohli

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

- ganeshie8

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

- ganeshie8

How many locations are there for placing 4 bars ?

- ParthKohli

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

- ganeshie8

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

- ganeshie8

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

Ew...

- ganeshie8

lets do one more example problem

- ParthKohli

Wow, OK.

- ganeshie8

find number of nonnegative integer solutions to the equation
\(a+b+c = 5\)

- ganeshie8

you want to partition \(5\) into \(3\) parts
so consider \(5\) stars and \(2\) bars

- ParthKohli

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

- ganeshie8

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

- ganeshie8

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

- ParthKohli

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

- ParthKohli

Thanks!

- ganeshie8

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

- ganeshie8

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

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

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

- ganeshie8

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

- ParthKohli

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

\(\large \star | |\star \star \star| \star \star | \star\)
two adjacent bars is not allowed

- ParthKohli

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

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

- ganeshie8

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

- ganeshie8

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

- ParthKohli

oh nice! let me answer this

- ParthKohli

|dw:1442673808024:dw|

- ganeshie8

Okay, clearly we cannot put a bar on left most or right most..
try to figure out the number of locations available for the \(4\) bars to go

- ParthKohli

wait, OHHHH

- ganeshie8

|dw:1442673856670:dw|

- ParthKohli

yes, I'm stupid...

- ganeshie8

6 locations available
4 bars to place
you can work the total number of ways to place 4 bars in 6 locations

- ParthKohli

yay

- ParthKohli

so that is where the\[\binom{n-1}{k-1}\]comes from

- ganeshie8

Yep

- ParthKohli

That's great.

- ParthKohli

Do you know rotational mechanics?

- ganeshie8

In general :
For the equation \(x_1 + x_2 + \cdots + x_k = n \),
1) number of "nonnegative" integer solutions is \(\dbinom{n+k-1}{k-1}\)
2) number of "positive" integer solutions is \(\dbinom{n-1}{k-1}\)

- ParthKohli

yup, that's what I got too. great.

- ganeshie8

that sounds like physics ?

- ParthKohli

yeah, physics :P

- ganeshie8

uniform circular motion or something more advanced ?

- ParthKohli

oh, wait, you didn't study rotational mechanics in high-school/engineering?

- ganeshie8

never heard of that name before

- ParthKohli

torque/angular momentum/moment of inertia/angular velocity/angular acceleration

Looking for something else?

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