So this forum doesn't atrophy completely...

I have 500 coins, and four bags. In how many ways can I put these coins in bags so that all coins are in a bag, and some bag may be empty. (Only count essentially different combinations, order doesn't matter-200, 150, 100, 50 is the same as 50, 100, 150, 200.) The total number is very large, and the best way i can find to do it is very difficult and time-consuming. I would be very impressed if anyone gets it, and it would be cool if they got the same answer as i did (mine could be a bit off ...)

500,0,0,0.
One bag with all the coins in it.
I think this meets your description for all the coins in a bag.

Originally posted by royalchicken
I have 500 coins, and four bags. In how many ways can I put these coins in bags so that all coins are in a bag, and some bag may be empty. (Only count essentially different combinations, order doesn't matter-200, 150, 100, 50 is the same as 50, 100, 150, 200.) The total number is very large, and the best way i can find to do it is very difficult and ...[text shortened]... gets it, and it would be cool if they got the same answer as i did (mine could be a bit off ...)

Assuming the coins are identical and not unique, then I could assume it's the combination of 500 in 5 (the empty bag):

500!
---------
5! x 495!

or 496x497x498x499x500 : (2x3x4x5)
=

127 622 343 800. Or am I wrong (again)?

Gil.

I may have expressed the question wrong. I am essentially looking for the total number of 4-tuples of nonnegative integers that add up to 500. I used two methods, which are essentially the same, but very tedious.

Originally posted by sintubin
Assuming the coins are identical and not unique, then I could assume it's the combination of 500 in 5 (the empty bag):

500!
---------
5! x 495!

or 496x497x498x499x500 : (2x3x4x5)
=

127 622 343 800. Or am I wrong (again)?

Gil.

this was wrong anyway. The possibility of an empty bag could not be represented by a fith bag.

It is much more complicated.

That's true. The answer is smaller than that by several orders of magnitude.

I think I've got something, but it's ugly and I don't know how to tidy it up. Consider whether any two bags have the same number of coins in them. Exactly one of the following is true:

a all bags have 125 coins.
b 3 bags same, 1 different.
c 2 pairs of bags.
d A pair and two distinct.
e All distinct.

There is only 1 possibility for a.
For b, 500/3 = 166 (rounded down), so there are 166 possibilites (+1 for 3 empty bags, -1 for case a)
For c, the pair with the least coins could have between 0 and 124 each, so 125 possibilities.

Now it gets ugly. Suppose we have a string of 500 0s and 2 1s. For every pair of 0s, put 1 coin in each of the first two bags until you reach the first 1. Then put a coin for every 0 into bag 3 until you reach the second 1, then put the remaining coins in bag 4. Now there are 251 choose 2 strings (=125*251) where both 1s occur in an odd position, so these are valid; and there are 251^2 strings where one is in an even and one in an odd position. In (251/2)(251+1) (=126*251) of these the odd one occurs first so these are also valid. This gives 251^2. However among these strings, 1 falls under case a; 2*166 fall under case b (3rd or 4th bag same as 1st two); and 2*125 fall under case c (larger pair could be 1&2 or 3&4). The order of the 3rd and 4th bags doesn't matter, so the remainder of the strings occur in equivalent pairs. This gives a total of [(251^2 - 1)/2 - 166 - 125] for case d, and a total of (251^2+1)/2 overall.

Finally, most of the possibilities are in case e: this time we have a string with 500 0s and 3 1s, with the obvious interpretation. There are 503 choose 3 (=167*251*503) of these. However amongst these 1 falls under a, 4*166 under b, 6*125 under c and 12*[(251^2 - 1)/2 -166 -125] under d (consider possible orders of bags). The rest occur in equivalence classes of 24.

So we have a grand total of {167*251*503 - 1 - 4*166 - 6*125 - 12*[(251^2 - 1)/2 - 166 -125]}/24 + (251^2 + 1)/2.

I think this is [167*251*503 - 1 + 8*166 + 6*(251^2 + 128)]/24, but I've probably made some mistakes along the way, and don't really want to simplify this expression any more. My calculator says 894348; does this sound right?
I'm sure you came up with a more elegant method than this!

Congratulations! You are exactly right. My METHOD was less elegant than that, although it involved proving a fairly groovy theorem. Let P(m, n) be the number of ways of dviding n into at most m addends. Thus we are looking for P(4, 500)-P(3, 500). I then proved that for real x such that |x|<1:

[(1-x)(1-x^2)(1-x^3)...(1-x^m)]^-1 = 1 + P(m, 1)x + P(m, 2)x^2+ ...

So all we are looking for are the 500th coefficients in the Maclaurin series expansion of (1-x)(1-x^2)(1-x^3)^-1, and the same times 1/(1-x^4). We can now do either of two things, namely:

Take the 500th order derivative of each of these at 0, divide each by 500!, and subtract (by Taylor's theorem), or factor these functions and find their Maclaurin expansions by multiplication of the series of each of the factors. The first method is ridiculously tedious, but the second is only absurdly tedious, and yields 894348. I thought somehow that this would be settled when you weighed in on this one. 'Grats.

You guys are freakin nuts in here! Hehehe...Just kidding! Kudos for the answer!

I know. You should come here more often 😉

I saw this thread again yesterday, and had a few minutes. I figured, in view of the very fine and clear solution Acolyte produced, that I should try to solve this one in a way not involving large infinite series. So I found another interesting way.

Let f(n,m) be the number of ways of representing n as the sum of at most m positive integers. Then it is fairly easy to prove that:

f(n,m) = f(n-m,m) + f(n,m-1)

Furthermore, if we want to find f(n,2), we can arrange the numbers in columns so that rows sum to n:

0....n
1....n-1
...
n....0

Clearly there is repetition here, so f(n,2) = [n/2] +1. Using the above recursion formula with this gives:

f(500,4) = SUM([n=1 to 125] SUM([k=0 to 4n/3] [(4n-3k)/2] + [4n/3]))

Adding these up gives 894348. 'Tis nice.

Good effort lad

Originally posted by waldorf
Good effort lad

Thank you. Approximately who are you? Can you prove the recursion formula...?

Originally posted by royalchicken
Thank you. Approximately who are you? Can you prove the recursion formula...?

Wat????????????

Originally posted by royalchicken
Thank you. Approximately who are you? Can you prove the recursion formula...?

erm-yeah-what's the recursion formula (i've heard of it before, but i ca't remeber what it is...😕)