Distributing N indistinguishable balls into M piles

[Mayan Fung]

TL;DR Summary

How to count the number of ways to distribute N balls into M piles where the balls are indistinguishable?

If there are N distinguishable boxes and M indistinguishable balls, the answer is easy as it is equivalent to the combinations of arranging N 0s and (M-1) 1s in a queue.

$$\binom{M+N-1}{N}$$

However, if the boxes are themselves indistinguishable (which I name them "piles" instead), how should I compute the number of combinations there? For example, I have 4 balls being distributed to 3 piles, the combinations should be (4,0,0), (3,1,0), (2,2,0), (2,1,1) only. So the number of ways = 4. I wonder if there is a simple way to compute the general case for M indistinguishable balls into N piles.

 

[Dale]

How can you have indistinguishable piles?

 

[mathman]

Multinomial distribution. $\frac{M!}{n_1!...n_N!}$ where $\sum_{k=1}^N n_k =M$.

 

[Mayan Fung]

How can you have indistinguishable piles?

I shall rephrase it. Whether which pile is which is not important, therefore, (3,0,0) (0,3,0) and (0,0,3) are considered as one case.

Multinomial distribution. $\frac{M!}{n_1!...n_N!}$ where $\sum_{k=1}^N n_k =M$.

The number of balls in each pile is not fixed. The only variable here is N and M

 

[Dale]

I shall rephrase it. Whether which pile is which is not important, therefore, (3,0,0) (0,3,0) and (0,0,3) are considered as one case.

Ah. Ok, then all you need to do is to do your previous calculation and then divide by the number of permutations of $M$ elements, which is just $M!$.

 

[PeroK]

Ah. Ok, then all you need to do is to do your previous calculation and then divide by the number of permutations of $M$ elements, which is just $M!$.

That's not going to work. For example, for $3$ distinguishable boxes and $4$ balls we have $15$ possibilities, but only $4$ different patterns: 4-0-0, 3-1-0, 2-2-0, 2-1-1.

 

[PeroK]

$$\binom{M+N-1}{N}$$

This should be $$\binom{M+N-1}{N-1} \ \text{or} \ \binom{M+N-1}{M}$$E.g. with $M =3, N = 4$ there are $15$ possibilities. Where $N$ is the number of boxes.

 

[Mayan Fung]

Ah. Ok, then all you need to do is to do your previous calculation and then divide by the number of permutations of $M$ elements, which is just $M!$.

i guess you are saying N! However, only if the number of balls in every pile, then I will be counted for N! times. For example, (321) (312) (213) (231) (123) (132). But, for example, (300) is only counted for 3 times instead of 3!. Simply dividing by N! doesn’t work.

I am afraid that I didn’t state the question clearly. Let’s say I have 5 balls and 3 boxes. If the boxes are distinguishable, then the number of combinations should (5+3-1)C3 = 7C3 = 7!/(3!4!) = 35

however, if the order of the boxes do not matter, then there are only 5 cases: (5,0,0), (4,1,0), (3,2,0),(3,1,1),(2,2,1)

 

[PeroK]

I am afraid that I didn’t state the question clearly. Let’s say I have 5 balls and 3 boxes. If the boxes are distinguishable, then the number of combinations should (5+3-1)C3 = 7C3 = 7!/(3!4!) = 35

This is still wrong. It should be $21$, not $35$.

 

[Mayan Fung]

This is still wrong. It should be $21$, not $35$.

you are right, that’s 7C2 not 7C3. So that’s 21

 

[PeroK]

I suspect this is very difficult. First, if $N \ge M$ (i.e. more boxes than balls) we have the following options:

M
M-1, 1
M-2, 2
M-2, 1 1
M-3, 3
M-3, 2, 1
M-3, 1, 1, 1

All the way to:

1, 1, ... 1

In general, if $N < M$, then you have to restrict the above to cases where there each list is at most $N$ long.

 

[PeroK]

PS The first of these (without the limitation) is the sequence of partition numbers for $M$:

https://oeis.org/A000041

 

[Mayan Fung]

PS The first of these (without the limitation) is the sequence of partition numbers for $M$:

https://oeis.org/A000041

Ya, I also just thought of that. Thank you for your help.

 

[Dale]

i guess you are saying N! However, only if the number of balls in every pile, then I will be counted for N! times. For example, (321) (312) (213) (231) (123) (132). But, for example, (300) is only counted for 3 times instead of 3!. Simply dividing by N! doesn’t work.

I am afraid that I didn’t state the question clearly. Let’s say I have 5 balls and 3 boxes. If the boxes are distinguishable, then the number of combinations should (5+3-1)C3 = 7C3 = 7!/(3!4!) = 35

however, if the order of the boxes do not matter, then there are only 5 cases: (5,0,0), (4,1,0), (3,2,0),(3,1,1),(2,2,1)

Ok, so the boxes are distinguishable but only by the number of balls in the box. That is tricky.

 

[PeroK]

Ok, so the boxes are distinguishable but only by the number of balls in the box. That is tricky.

Yes, definitely tricky. There's nothing about it here:

https://en.wikipedia.org/wiki/Partition_(number_theory)#Restricted_partitions