A community for students.

Here's the question you clicked on:

55 members online
  • 0 replying
  • 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.

  • This Question is Closed
  1. ParthKohli
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    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.

  2. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Srry im just starting alg 1

  3. ParthKohli
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    We all start there.

  4. ParthKohli
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    @ganeshie8 any ideas?

  5. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  6. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  7. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  8. ParthKohli
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  9. ParthKohli
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    How do we work with this?

  10. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    Yes, stars and bars is just a visualization technique

  11. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  12. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  13. ParthKohli
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  14. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  15. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  16. ParthKohli
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    1, 1, 0, 4, 1

  17. ParthKohli
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  18. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  19. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    How many locations are there for placing 4 bars ?

  20. ParthKohli
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  21. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  22. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 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}\)

  23. ParthKohli
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    Ew...

  24. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    lets do one more example problem

  25. ParthKohli
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    Wow, OK.

  26. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  27. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  28. ParthKohli
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  29. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  30. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  31. ParthKohli
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  32. ParthKohli
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    Thanks!

  33. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  34. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  35. ParthKohli
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 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 ...

  36. ParthKohli
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  37. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  38. ParthKohli
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    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.

  39. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  40. ParthKohli
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    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.

  41. ParthKohli
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  42. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  43. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  44. ParthKohli
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    oh nice! let me answer this

  45. ParthKohli
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    |dw:1442673808024:dw|

  46. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    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

  47. ParthKohli
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    wait, OHHHH

  48. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    |dw:1442673856670:dw|

  49. ParthKohli
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    yes, I'm stupid...

  50. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  51. ParthKohli
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    yay

  52. ParthKohli
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  53. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    Yep

  54. ParthKohli
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    That's great.

  55. ParthKohli
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    Do you know rotational mechanics?

  56. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    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}\)

  57. ParthKohli
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  58. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    that sounds like physics ?

  59. ParthKohli
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    yeah, physics :P

  60. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    uniform circular motion or something more advanced ?

  61. ParthKohli
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  62. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    never heard of that name before

  63. ParthKohli
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

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

    • Attachments:

Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy

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
  • 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.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.