klimenkov
  • klimenkov
How many non-negative integer solutions does this equation have? \[x_1+x_2+\ldots+x_N=n\]
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!
cruffo
  • cruffo
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.
klimenkov
  • klimenkov
They are different.
experimentX
  • experimentX
woops!! that's for ... a+b+c+d = N

Looking for something else?

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

More answers

cruffo
  • cruffo
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.
experimentX
  • experimentX
a+b = n would make n+1 solutions a +b + c = n would make |dw:1350155772870:dw|
experimentX
  • experimentX
probably we would add up (summation) n-2 times for n+1
klimenkov
  • klimenkov
Hm.. I would like you to write the whole solution and the expression as an answer.
experimentX
  • experimentX
honestly I don't know any closed form for this.
cruffo
  • cruffo
who are you taking to? @experimentX or me?
cruffo
  • cruffo
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.
klimenkov
  • klimenkov
You both. I know the answer. I found this problem very interesting.
cruffo
  • cruffo
you just need to generalize...
experimentX
  • experimentX
well ... one thing is for sure ... it must have something with to do of the order of N^(N+1)
cruffo
  • cruffo
You have n units and (N-1) s's. How many ways can you select (N-1) things out of (n-1)
klimenkov
  • klimenkov
Think again. In an hour I will give you an answer.
experimentX
  • experimentX
1:15 am here ...
klimenkov
  • klimenkov
Do you want it now?
experimentX
  • experimentX
I'll wait till tomorrow.
klimenkov
  • klimenkov
@cruffo 's method is very good. But he must correct it.
cruffo
  • cruffo
Right, the are are a few solutions missing - the ones that start with 0 or end in 0
experimentX
  • experimentX
probably this is related to this http://en.wikipedia.org/wiki/Partition_(number_theory)
cruffo
  • cruffo
why not just add s's at the beginning and end of the sequence...
cruffo
  • cruffo
never mind...that won't take care of the others...
experimentX
  • experimentX
can x's be zero?
cruffo
  • cruffo
yes, it can, as can any of the variables. But my take on the problem excludes those possibilities.
cruffo
  • cruffo
My solution won't allow for adjacent s's
cruffo
  • cruffo
Claim: every arrangement of n u's and (N-1) s's gives a solution.
cruffo
  • cruffo
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)
experimentX
  • experimentX
so C(n+N-1, N-1) is your solution?
experimentX
  • experimentX
|dw:1350157242721:dw|
experimentX
  • experimentX
|dw:1350157497037:dw|
experimentX
  • experimentX
can't think at the moment ... Night!! will see solution tomorrow directly. Nevertheless combinatorics has never been my stuff.
cruffo
  • cruffo
"Mathematics of Choice" by Ivan Niven http://books.google.com/books?id=UrVQYgEACAAJ The best introductory book, IMHO
klimenkov
  • klimenkov
@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.
experimentX
  • experimentX
interesting!!
klimenkov
  • klimenkov
Did you understand or not?
experimentX
  • experimentX
yeah i see the picture ...
klimenkov
  • klimenkov
Very good!
experimentX
  • experimentX
never thought i would have such interestingly simple technique.
experimentX
  • experimentX
*it
klimenkov
  • klimenkov
Try to solve my next ploblem using similar method.
experimentX
  • experimentX
sure ..

Looking for something else?

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