How many ways are there to write 20 as a sum of 4 nonnegative integer
numbers, including zero?  If order does not matter and if it does. 
when it does not matter 20+0+0+0 and 0+20+0+0 are same.  when it does
they are different.

Hi! 

Thanks for your question!

Before I answer this question I'll just define a few things used in
the answer:

* = multiplied by
/ = divided by
! = mathematical factorial symbol

I'll explain the factorial symbol in case you don't know it:
n! is the multiplication of a number by (number - 1) by (number -2)
etc until 1 ie: n! = n*(n-1)*(n-2)*...*1
eg1.  4! = 4*3*2*1
eg2.  5! = 5*4*3*2*1

Now for the question:
Try looking at it another way,
Look at one particular solution, say 3+2+1+14=20.

You could represent this as:

***|**|*|**************       (these are stars not multiplication
symbols)
           
That is, the number of ways to partition 20 identical objects into 4
distinguishable cells.

Therefore the answer to this is:

((20+3)!)/(20!3!) = 1771    

(ie the number of ways to arrange 20 stars and 3 slashes, divided by
the number of ways the stars can arrange amongst themselves, and
divided by the number of ways the slashes can arrange amongst
themselve.)

If the order is important:

The answer is the same except multiplied by the number of ways each
solution of 4 numbers could be arranged in a line (ie 4!)

ie answer is ((20+3)!*4!)/(20!3!)   = 42504

Summary:
The number of ways to add four non negative numbers to give 20:
1. Order doesn't matter = 1771
2. Order does matter = 42504

Search terms used:
none

Reference:
Occupancy Model, statistics

Hope this helps, if you don't understand this, please ask for a
clarification

Cheers,

Jenjerina

---

Request for Answer Clarification by brkyrhrt99_00-ga on 07 Sep 2002 08:43 PDT

Since the cooment was posted I am a little confused.  Please clarify.

---

Clarification of Answer by jenjerina-ga on 08 Sep 2002 15:40 PDT

Hi,

Thanks for your clarification brkyrhrt99_00-ga and for your comment
websearcher-ga. Of course I should have realised that the number of
ways to add those numbers together when order doesn't matter should be
much less than when order does matter!

I agree with websearcher-ga that the correct answer to when order does
matter is 1771. With websearcher-ga's answer of 108, that is probably
right but I'll research how to work this answer out mathematically.

Thanks again,

Jenjerina

---

Clarification of Answer by jenjerina-ga on 09 Sep 2002 04:59 PDT

Hi brkyrhrt99_00-ga,

I'm happy to say I have the correct answer for you.

I asked a professor in statistics at a university over here. Turns out
there is no MATHEMATICAL way to work out the sum of 4 non negative
integers to 20 when order doesn't matter. Apparently many have tried
and failed to come up with a formula but one can not be found. The
only way to work it out is to recursively look at all possibilities
which is best done with a computer. So websearcher's answer of 108 is
correct and websearcher has worked it out in the only way possible.

To help you in future, the number of solutions in non-negative
integers to the equation x1 + x2 + .... xn = r (where order does
matter) is given by the formula:
(n + r - 1)!/(r!(n-1)!)  

If you understand combination notation, this formula is equivalent to
(n+r-1)C(r) where the (n+r-1) is postscript and the (r) is subscript
of the C.

I'm very sorry to have made a mistake with your question and I hope
this clarifies it. If not, please request another clarification.

Thanks for your patience and thanks again websearcher-ga,

Jenjerina-ga

excellent

Hi brkyrhrt99_00-ga:

I think jenjerina-ga may have made a simple - yet important - error in
the logic to her answer above.

Using the stars and slashes analogy was valid, but it needs to be
looked at a little bit differently. Actually, the way she has it set
up above for when order doesn't matter is exactly the way it should be
set up when ordering DOES matter.

To illustrate this, in your original question you state:

"when it does not matter 20+0+0+0 and 0+20+0+0 are same.  when it does
they are different."

Using jenjerina-ga's stars and slashes, these two results would be

********************|||

|********************||

*Both* of these would have been counted in jenjerina-ga's original
formula. In fact, you can see that it would be quite easy to create
more "duplicate" results using the stars and slashes:

***|*******|*****|*****
*******|*****|***|*****

Both of these would equate to 3+5+5+7 (if you ignore ordering). 

So, I believe that jenjerina-ga's original formula of 

((20+3)!)/(20!3!) = 1771     

is correct, but for the number when order *DOES* count. 

I verified this using Maple (a computer algebra system) and it turns
out that 1771 *is* the correct number of compositions when order does
matter. The correct number of composiions when order doesn't matter is
108. They are as follows:

[0, 0, 0, 20], [0, 0, 1, 19], [0, 0, 9, 11], [0, 0, 8, 12], [0, 0, 10,
10], [0, 0, 7, 13], [0, 0, 5, 15], [0, 0, 6, 14], [0, 0, 2, 18], [0,
0, 3, 17], [0, 0, 4, 16], [0, 1, 9, 10], [0, 2, 5, 13], [0, 3, 7, 10],
[0, 2, 7, 11], [0, 2, 6, 12], [0, 4, 7, 9], [0, 1, 2, 17], [0, 2, 2,
16], [0, 5, 7, 8], [0, 1, 6, 13], [0, 1, 7, 12], [0, 4, 5, 11], [0, 4,
6, 10], [0, 2, 4, 14], [0, 3, 3, 14], [0, 1, 4, 15], [0, 1, 5, 14],
[0, 2, 3, 15], [0, 2, 9, 9], [0, 2, 8, 10], [0, 1, 1, 18], [0, 5, 5,
10], [0, 1, 8, 11], [0, 3, 8, 9], [0, 6, 7, 7], [0, 1, 3, 16], [0, 3,
4, 13], [0, 3, 5, 12], [0, 3, 6, 11], [0, 4, 4, 12], [0, 4, 8, 8], [0,
5, 6, 9], [0, 6, 6, 8], [1, 4, 7, 8], [1, 3, 7, 9], [3, 4, 5, 8], [2,
3, 7, 8], [1, 3, 8, 8], [1, 2, 8, 9], [1, 1, 8, 10], [1, 5, 6, 8], [2,
3, 3, 12], [2, 2, 8, 8], [2, 4, 6, 8], [2, 5, 5, 8], [3, 3, 6, 8], [4,
4, 4, 8], [2, 4, 4, 10], [2, 2, 5, 11], [2, 3, 6, 9], [1, 3, 5, 11],
[1, 4, 6, 9], [2, 2, 7, 9], [1, 1, 1, 17], [2, 4, 5, 9], [3, 3, 7, 7],
[1, 2, 4, 13], [4, 5, 5, 6], [3, 3, 5, 9], [1, 1, 9, 9], [1, 1, 7,
11], [2, 5, 6, 7], [1, 2, 7, 10], [1, 2, 3, 14], [1, 3, 3, 13], [1, 1,
4, 14], [2, 4, 7, 7], [3, 5, 6, 6], [3, 4, 4, 9], [2, 3, 4, 11], [1,
5, 7, 7], [1, 1, 5, 13], [1, 5, 5, 9], [3, 3, 3, 11], [4, 4, 5, 7],
[1, 2, 6, 11], [1, 4, 5, 10], [2, 2, 6, 10], [1, 2, 5, 12], [1, 1, 6,
12], [1, 6, 6, 7], [2, 3, 5, 10], [1, 3, 4, 12], [1, 3, 6, 10], [3, 4,
6, 7], [2, 2, 2, 14], [1, 1, 3, 15], [1, 1, 2, 16], [2, 6, 6, 6], [1,
2, 2, 15], [2, 2, 3, 13], [3, 3, 4, 10], [2, 2, 4, 12], [4, 4, 6, 6],
[3, 5, 5, 7], [1, 4, 4, 11], [5, 5, 5, 5]

I don't know what the formula would be to get this figure of 108. I
used a more brute-force method to arrive with that figure and the
above list.

Hope this helps. 

websearcher-ga

Well, it's reassuring to find out that there is no formula for the
number of compositions when order doesn't matter. It's been bugging me
ever since I posted my first comment! :-) :-)

Anyway, now I can let it go. 

You are most welcome jenjerina-ga. Helping out is what we're here for.

websearcher-ga