Quantcast

Got Homework?

Connect with other students for help. It's a free community.

  • across
    MIT Grad Student
    Online now
  • laura*
    Helped 1,000 students
    Online now
  • Hero
    College Math Guru
    Online now

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

klimenkov

How many non-negative integer solutions does this equation have? \[x_1+x_2+\ldots+x_N=n\]

  • one year ago
  • one year ago

  • This Question is Closed
  1. cruffo
    Best Response
    You've already chosen the best response.
    Medals 2

    Are you considering the solutions to be ordered or unordered? For example, if we wee trying to solve: x + y + z + w = 12 Would the solution (x,y,z,w) = (9,1,1,1) = (1,9,1,1) = (1,1,9,1) = (1,1,1,9) or would that be considered 4 separate solutions? If they are considered the same, then this is a partitions problem, if they are different, then this is a combinations problem.

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

    They are different.

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

    woops!! that's for ... a+b+c+d = N

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

    For the smaller example: x + y + z + w = 12 The number of solutions can be determined by viewing the problem in the following way: If 12 units (denoted as 12 u's) seperated by 11 spaces (denoted by 11 s's) are lined up, usususususususususususu and we choose any 3 of the s's and let the others disappear, for example: u u s u u u usu u u u usu then the remaining s's seperate the units into four batches. The number of units in these batches can be used as the values of x,y,z, and w.

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

    a+b = n would make n+1 solutions a +b + c = n would make |dw:1350155772870:dw|

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

    probably we would add up (summation) n-2 times for n+1

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

    Hm.. I would like you to write the whole solution and the expression as an answer.

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

    honestly I don't know any closed form for this.

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

    who are you taking to? @experimentX or me?

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

    For mine, any selection of three s's gives a solution. Thus, the number of solutions is the same as the number of ways of selection 3 things out of 11.

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

    You both. I know the answer. I found this problem very interesting.

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

    you just need to generalize...

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

    well ... one thing is for sure ... it must have something with to do of the order of N^(N+1)

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

    You have n units and (N-1) s's. How many ways can you select (N-1) things out of (n-1)

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

    Think again. In an hour I will give you an answer.

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

    1:15 am here ...

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

    Do you want it now?

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

    I'll wait till tomorrow.

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

    @cruffo 's method is very good. But he must correct it.

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

    Right, the are are a few solutions missing - the ones that start with 0 or end in 0

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

    probably this is related to this http://en.wikipedia.org/wiki/Partition_(number_theory)

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

    why not just add s's at the beginning and end of the sequence...

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

    never mind...that won't take care of the others...

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

    can x's be zero?

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

    yes, it can, as can any of the variables. But my take on the problem excludes those possibilities.

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

    My solution won't allow for adjacent s's

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

    Claim: every arrangement of n u's and (N-1) s's gives a solution.

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

    so you have a total of n + (N-1) things and you choose where to place (N-1) of them: C(n+N-1, N-1)

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

    so C(n+N-1, N-1) is your solution?

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

    |dw:1350157242721:dw|

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

    |dw:1350157497037:dw|

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

    can't think at the moment ... Night!! will see solution tomorrow directly. Nevertheless combinatorics has never been my stuff.

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

    "Mathematics of Choice" by Ivan Niven http://books.google.com/books?id=UrVQYgEACAAJ The best introductory book, IMHO

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

    @cruffo is right. I will write a full solution. Let's make a simple model of this problem. Imagine that we have \(n\) balls. There is no matter what is first, what is the second,..., they are all the same. And we have \(N\) boxes where to put this balls. You can put this \(n\) balls in any box that you like. On the picture there are some ways how to put 10 balls into 5 boxes. The number of the balls in the first box is \(x_1\), in the second - \(x_2\) ... in the \(N\)-th - \(x_N\).|dw:1350209158710:dw| Lets make the side of the box as 1 and about the ball as 0. Every placement of the balls in this boxes can be shown as the sequence of \(n+N+1\) zeros and 1's. For \(n=5\) and \(N=10\) an example will be 1000011000011001. But the first and the last term in this sequence must be 1 because they are the sides of the box. If we shift 0's and 1's inside the first and the last 1's we will get the new arrangement in the boxes. But we can replace only \((n+N+1)-2=n+N-1\) terms in the sequence. If we choose the places for 1's the place for 0's will be chosen automatically. So we can choose the place for 1's in \(\left(\begin{matrix}n+N-1 \\ N-1\end{matrix}\right)\) ways because we can shift \(N-1\) 1's. Or we can shift 0's. then we will have \(\left(\begin{matrix}n+N-1 \\ n\end{matrix}\right)\) ways. This will be an answer. Hope you understood and enjoyed this interesting problem.

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

    interesting!!

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

    Did you understand or not?

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

    yeah i see the picture ...

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

    Very good!

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

    never thought i would have such interestingly simple technique.

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

    *it

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

    Try to solve my next ploblem using similar method.

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

    sure ..

    • one year ago
    • Attachments:

See more questions >>>

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.