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

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.

Get our expert's

answer on brainly

SEE EXPERT ANSWER

Get your free account and access expert answers to this and thousands of other questions.

A community for students.

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

Mathematics
See more answers at brainly.com
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.

Get this expert

answer on brainly

SEE EXPERT ANSWER

Get your free account and access expert answers to this and thousands of other questions

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.
Srry im just starting alg 1
We all start there.

Not the answer you are looking for?

Search for more explanations.

Ask your own question

Other answers:

@ganeshie8 any ideas?
This is stars and bars problem Consider \(n+k\) stars and \(n-1\) bars
Before generalizing, maybe lets work an example problem by giving specific numbers to \(k\) and \(n\)
How about \(n=5\) and \(k=13\) Find the number of nonnegative integer solutions to the equation \(a+b+c+d+e = 13\)
Yes. Is the "stars-and-bars" idea better to work with and think about? I can see why they're the same problems though.
How do we work with this?
Yes, stars and bars is just a visualization technique
13 is kinda large, lets try a much simpler example : \(a+b+c+d+e = 7 \)
Consider \(7\) stars and \(4\) bars : \(\star |\star| \star \star| \star \star| \star \)
Yes, a = 1, b = 1, c = 2, d = 2, e = 1
above arrangement represents a solution : \((1,1,2,2,1)\)
right, what about below \(\star |\star| |\star \star \star \star| \star\)
1, 1, 0, 4, 1
I see what it represents, but it doesn't get us any closer to solving the question though, right?
Notice that the problem translates to finding number of ways of "placing" the four bars between the seven stars
How many locations are there for placing 4 bars ?
That's what we have to figure out...
Isn't it trivial to figure that out just by looking at the stars and bars ?
\(\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}\)
Ew...
lets do one more example problem
Wow, OK.
find number of nonnegative integer solutions to the equation \(a+b+c = 5\)
you want to partition \(5\) into \(3\) parts so consider \(5\) stars and \(2\) bars
Where did you come up with 7 + 4? Theoretically, I could place all the four bars to the left of all seven stars.
sure, you can, thats one solution : \((0,0,0,0,7)\)
\(||||\star \star \star \star \star \star \star\) Notice that the length of above string doesn't change, it is still \(11\)
Oh, so I had to look at it as a string! Nice.
Thanks!
if it helps, yeah.. it is a simple concept but many combinatorics problems keep refering to this concept..
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\)
\[\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 ...
Am I missing something? Is that the number of nonnegative solutions too?
Nope. How is that different from the earlier problem of finding number of "nonnegative" integer solutions ?
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.
\(\large \star | |\star \star \star| \star \star | \star\) two adjacent bars is not allowed
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.
So the number of positive solutions is \(\binom{11}{4} - \binom{10}3\) ...?
that might work we could also use the previous trick : simply consider the number of locations for bars
\(7\) stars : \(\star~~\star~~\star~~\star~~\star~~\star~~\star \) where can the \(4\) bars go ?
oh nice! let me answer this
|dw:1442673808024:dw|
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
wait, OHHHH
|dw:1442673856670:dw|
yes, I'm stupid...
6 locations available 4 bars to place you can work the total number of ways to place 4 bars in 6 locations
yay
so that is where the\[\binom{n-1}{k-1}\]comes from
Yep
That's great.
Do you know rotational mechanics?
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}\)
yup, that's what I got too. great.
that sounds like physics ?
yeah, physics :P
uniform circular motion or something more advanced ?
oh, wait, you didn't study rotational mechanics in high-school/engineering?
never heard of that name before
torque/angular momentum/moment of inertia/angular velocity/angular acceleration

Not the answer you are looking for?

Search for more explanations.

Ask your own question