# Distributing N indistinguishable balls into M piles

• B
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
Mentor
2020 Award
How can you have indistinguishable piles?

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

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
Mentor
2020 Award
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
Homework Helper
Gold Member
2020 Award
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
Homework Helper
Gold Member
2020 Award
$$\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.

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)

Dale
PeroK
Homework Helper
Gold Member
2020 Award
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##.

This is still wrong. It should be ##21##, not ##35##.
you are right, that’s 7C2 not 7C3. So that’s 21

PeroK
Homework Helper
Gold Member
2020 Award
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
Homework Helper
Gold Member
2020 Award
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
Mentor
2020 Award
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.

Mayan Fung
PeroK