B Distributing N indistinguishable balls into M piles

Mayan Fung
Messages
131
Reaction score
14
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.
 
Physics news on Phys.org
How can you have indistinguishable piles?
 
Multinomial distribution. ##\frac{M!}{n_1!...n_N!}## where ##\sum_{k=1}^N n_k =M##.
 
Dale said:
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.
mathman said:
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
 
Mayan Fung said:
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!##.
 
Dale said:
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.
 
Mayan Fung said:
$$\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.
 
Dale said:
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)
 
  • Like
Likes Dale
Mayan Fung said:
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##.
 
  • #10
PeroK said:
This is still wrong. It should be ##21##, not ##35##.
you are right, that’s 7C2 not 7C3. So that’s 21
 
  • #11
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.
 
  • #12
PS The first of these (without the limitation) is the sequence of partition numbers for ##M##:

https://oeis.org/A000041
 
  • Like
Likes Mayan Fung
  • #13
PeroK said:
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.
 
  • #14
Mayan Fung said:
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.
 
  • Like
Likes Mayan Fung
Back
Top