Probability – Combinatorics?

Question

How many ways are there to put n balls into r boxes if:

1) Both the balls and the boxes are distinct
2) The boxes are distinct but the balls are not distinct
3) The balls are distinct but the boxes are not distinct
4) Neither the balls nor the boxes are distinct

You can put more than one ball into a box.

Answer 1

The cases 1) and 2) are well-known.

1) The 1st ball can be in any of r boxes /r choices/, the same is true about the 2nd ball, etc. to the last one, i.e. we obtain
r*r*. . . *r = r^n arrangements.
Example: 3 balls in 2 boxes: 8 = 2³ arrangements:
(123|-), (12|3), (23|1), (31|2), (1|23), (2|31), (3|12), (-|123)

2) This is the number of solutions of the Diophantine equation
x_1 + x_2 + x_3 + . . + x_r = n, x_i ≥ 0, integer, i=1,2,..r
It is the binomial coefficient {n}_C_{n+r-1} = (r-1}_C_{n+r-1}
Example: 3 balls in 2 boxes: 3_C_4 = 1_C_4 = 4 arrangements:
(ooo|-), (oo|o), (o|oo), (-|ooo)
The same is the number of the partial derivatives of nth order of a differentiable function of r variables:
F(x,y) has F'"xxx, F'"xxy, F'"xyy, F'"yyy

4) This is the number of partitions of number n into r non-negative integer parts /or, solutions of the equation in 2) above with monotonous components/, for example
5 = 5+0+0 = 4+1+0 = 3+2+0 = 3+1+1 = 2+2+1
gives the possible arrangements of 5 non-distinct balls in 3 non-distinct boxes. There are many sources on the subject, but I haven't seen an expression in a closed form for it, the discussions involve mainly generating functions for these partitions, their asymptotic behavior and enumeration algorithms.

3) This seems the most difficult, the different partitions, mentioned in 4) above generate different number of permutations, again I haven't seen a convenient way to express the number of arrangements using the standard functions. For example, 3 distinct balls in 2 non-distinct boxes can be arranged (123|-), (12|3), (23|1), or (31|2).

Answer 2

Still no other answers? I suppose then I'll give the solutions I have so far:

(1) This one is fairly well known and simple. Consider the balls in turn. Each one has r places we can put it, and the choice of each ball is independent, so simply multiply n times, for r^n.

(2) This one is perhaps well known, but not as simple. Consider the non-distinct balls put in a row, and consider r markers for the boxes; we'll place the markers between the balls, in order of box number, and the number of balls appearing before a given box number is the number of balls in that box. We see immediately that box number r must be at the end of the row of balls. To see how many ways we can arrange the other r-1 balls, simply note that we'll have a list of n+(r-1) elements, and we need to know how many ways to pick (r-1) spots for specific elements. Therefore it's the choose function, C(n+r-1, r-1).

(3) I'm still working on this one. I thought we should be able to simply divide (1) by r!, the number of ways to permute the boxes, but then there's no reason r^n / r! should be integral. Looking at an example, I believe the problem to be when there are several boxes with no balls in them--we don't need to divide by a whole r! then.

(4) I have the same problem here as in (3).

...I'll keep working on these, but any enlightenment would certainly be helpful :)

EDIT: I was afraid one of (3) or (4) would boil down to a difficult "integer partition" problem, as Duke has suggested. I know there's a generating function for the number of ways to partition an integer, but I haven't heard of restricting the partitions to having a given number of non-empty subsets. By that I mean I'm used to having the partitions of 4 being
4
1+3
2+2
1+1+2
1+1+1+1,
but here we only consider those which have <=r components, so that if r=2, only the partitions 4, 1+3, and 2+2 count. I was hoping perhaps that (3) would actually be easier than (4), since our partitioning would be more structured. But perhaps I am mistaken.

Answer 3

I'll give it a try.

To make it easier.
Assume there are more balls than boxes ie n>r and that we are just putting one ball into each box???
Is this ok?

1)
Choose r balls to put in boxes, then arrange.
nCr x r!

2)
I think just 1.
Since the balls are not distinct.

3)
Choose r balls.
nCr


4) Again- just 1