ParthKohli
  • ParthKohli
Number of solutions to equation \(x_1 + x_2 + \cdots + x_n = k \) under the constraint that each variable here is nonnegative.
Mathematics
  • Stacey Warren - Expert brainly.com
Hey! We 've verified this expert answer for you, click below to unlock the details :)
SOLVED
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.
schrodinger
  • schrodinger
I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!
ParthKohli
  • 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
  • anonymous
Srry im just starting alg 1
ParthKohli
  • ParthKohli
We all start there.

Looking for something else?

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

More answers

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