A community for students.
Here's the question you clicked on:
 0 viewing
ParthKohli
 one year ago
Number of solutions to equation \(x_1 + x_2 + \cdots + x_n = k \) under the constraint that each variable here is nonnegative.
ParthKohli
 one year ago
Number of solutions to equation \(x_1 + x_2 + \cdots + x_n = k \) under the constraint that each variable here is nonnegative.

This Question is Closed

ParthKohli
 one year ago
Best ResponseYou've already chosen the best response.1I 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
 one year ago
Best ResponseYou've already chosen the best response.0Srry im just starting alg 1

ParthKohli
 one year ago
Best ResponseYou've already chosen the best response.1We all start there.

ParthKohli
 one year ago
Best ResponseYou've already chosen the best response.1@ganeshie8 any ideas?

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.1This is stars and bars problem Consider \(n+k\) stars and \(n1\) bars

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.1Before generalizing, maybe lets work an example problem by giving specific numbers to \(k\) and \(n\)

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.1How about \(n=5\) and \(k=13\) Find the number of nonnegative integer solutions to the equation \(a+b+c+d+e = 13\)

ParthKohli
 one year ago
Best ResponseYou've already chosen the best response.1Yes. Is the "starsandbars" idea better to work with and think about? I can see why they're the same problems though.

ParthKohli
 one year ago
Best ResponseYou've already chosen the best response.1How do we work with this?

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.1Yes, stars and bars is just a visualization technique

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.113 is kinda large, lets try a much simpler example : \(a+b+c+d+e = 7 \)

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.1Consider \(7\) stars and \(4\) bars : \(\star \star \star \star \star \star \star \)

ParthKohli
 one year ago
Best ResponseYou've already chosen the best response.1Yes, a = 1, b = 1, c = 2, d = 2, e = 1

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.1above arrangement represents a solution : \((1,1,2,2,1)\)

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.1right, what about below \(\star \star \star \star \star \star \star\)

ParthKohli
 one year ago
Best ResponseYou've already chosen the best response.1I see what it represents, but it doesn't get us any closer to solving the question though, right?

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.1Notice that the problem translates to finding number of ways of "placing" the four bars between the seven stars

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.1How many locations are there for placing 4 bars ?

ParthKohli
 one year ago
Best ResponseYou've already chosen the best response.1That's what we have to figure out...

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.1Isn't it trivial to figure that out just by looking at the stars and bars ?

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.1\(\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}\)

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.1lets do one more example problem

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.1find number of nonnegative integer solutions to the equation \(a+b+c = 5\)

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.1you want to partition \(5\) into \(3\) parts so consider \(5\) stars and \(2\) bars

ParthKohli
 one year ago
Best ResponseYou've already chosen the best response.1Where did you come up with 7 + 4? Theoretically, I could place all the four bars to the left of all seven stars.

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.1sure, you can, thats one solution : \((0,0,0,0,7)\)

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.1\(\star \star \star \star \star \star \star\) Notice that the length of above string doesn't change, it is still \(11\)

ParthKohli
 one year ago
Best ResponseYou've already chosen the best response.1Oh, so I had to look at it as a string! Nice.

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.1if it helps, yeah.. it is a simple concept but many combinatorics problems keep refering to this concept..

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.1what 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
 one year ago
Best ResponseYou've already chosen the best response.1\[\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
 one year ago
Best ResponseYou've already chosen the best response.1Am I missing something? Is that the number of nonnegative solutions too?

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.1Nope. How is that different from the earlier problem of finding number of "nonnegative" integer solutions ?

ParthKohli
 one year ago
Best ResponseYou've already chosen the best response.1Oh, 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
 one year ago
Best ResponseYou've already chosen the best response.1\(\large \star  \star \star \star \star \star  \star\) two adjacent bars is not allowed

ParthKohli
 one year ago
Best ResponseYou've already chosen the best response.1If 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
 one year ago
Best ResponseYou've already chosen the best response.1So the number of positive solutions is \(\binom{11}{4}  \binom{10}3\) ...?

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.1that might work we could also use the previous trick : simply consider the number of locations for bars

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.1\(7\) stars : \(\star~~\star~~\star~~\star~~\star~~\star~~\star \) where can the \(4\) bars go ?

ParthKohli
 one year ago
Best ResponseYou've already chosen the best response.1oh nice! let me answer this

ParthKohli
 one year ago
Best ResponseYou've already chosen the best response.1dw:1442673808024:dw

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.1Okay, 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

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.1dw:1442673856670:dw

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.16 locations available 4 bars to place you can work the total number of ways to place 4 bars in 6 locations

ParthKohli
 one year ago
Best ResponseYou've already chosen the best response.1so that is where the\[\binom{n1}{k1}\]comes from

ParthKohli
 one year ago
Best ResponseYou've already chosen the best response.1Do you know rotational mechanics?

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.1In general : For the equation \(x_1 + x_2 + \cdots + x_k = n \), 1) number of "nonnegative" integer solutions is \(\dbinom{n+k1}{k1}\) 2) number of "positive" integer solutions is \(\dbinom{n1}{k1}\)

ParthKohli
 one year ago
Best ResponseYou've already chosen the best response.1yup, that's what I got too. great.

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.1that sounds like physics ?

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.1uniform circular motion or something more advanced ?

ParthKohli
 one year ago
Best ResponseYou've already chosen the best response.1oh, wait, you didn't study rotational mechanics in highschool/engineering?

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.1never heard of that name before

ParthKohli
 one year ago
Best ResponseYou've already chosen the best response.1torque/angular momentum/moment of inertia/angular velocity/angular acceleration
Ask your own question
Sign UpFind more explanations on OpenStudy
Your question is ready. Sign up for free to start getting answers.
spraguer
(Moderator)
5
→ View Detailed Profile
is replying to Can someone tell me what button the professor is hitting...
23
 Teamwork 19 Teammate
 Problem Solving 19 Hero
 Engagement 19 Mad Hatter
 You have blocked this person.
 ✔ You're a fan Checking fan status...
Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.