Distributing N indistinguishable balls into M piles

  • #1
128
14
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.
 

Answers and Replies

  • #3
mathman
Science Advisor
8,008
518
Multinomial distribution. ##\frac{M!}{n_1!...n_N!}## where ##\sum_{k=1}^N n_k =M##.
 
  • #4
128
14
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
 
  • #5
Dale
Mentor
Insights Author
2020 Award
32,154
9,095
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!##.
 
  • #6
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
2020 Award
19,296
10,806
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.
 
  • #7
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
2020 Award
19,296
10,806
$$\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.
 
  • #8
128
14
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)
 
  • #9
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
2020 Award
19,296
10,806
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
128
14
This is still wrong. It should be ##21##, not ##35##.
you are right, that’s 7C2 not 7C3. So that’s 21
 
  • #11
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
2020 Award
19,296
10,806
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
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
2020 Award
19,296
10,806
PS The first of these (without the limitation) is the sequence of partition numbers for ##M##:

https://oeis.org/A000041
 
  • #14
Dale
Mentor
Insights Author
2020 Award
32,154
9,095
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.
 

Related Threads on Distributing N indistinguishable balls into M piles

  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
3
Views
472
Replies
2
Views
600
  • Last Post
Replies
1
Views
2K
Replies
2
Views
2K
Replies
9
Views
3K
Replies
2
Views
4K
  • Last Post
Replies
2
Views
2K
Replies
28
Views
13K
Top