Grouping the marbles

Probability Level 3

How many ways are there to distribute 15 identical marbles into 5 non-empty groups?

Note : The order of the groups does not matter.


The answer is 30.

Andy Hayes by Andy Hayes , 38, USA

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Andy Hayes
May 17, 2016

Relevant wiki: Identical Objects into Identical Bins

Let p ( n , r ) p(n,r) be the number of distributions of n n identical objects into r r identical bins, and let p ( n ) p(n) be the number of distributions of n n identical objects into any number of identical bins. (These are equivalent to the number of partitions of an integer into r r parts or any number of parts)

This problem is asking for p ( 15 , 5 ) p(15,5) .

We use a number of identities and theorems on the identical objects into identical bins page.

p ( 15 , 5 ) = p ( 10 , 1 ) + p ( 10 , 2 ) + p ( 10 , 3 ) + p ( 10 , 4 ) + p ( 10 , 5 ) = 1 + 5 + p ( 10 , 3 ) + p ( 10 , 4 ) + p ( 5 ) p(15,5)=p(10,1)+p(10,2)+p(10,3)+p(10,4)+p(10,5)=1+5+p(10,3)+p(10,4)+p(5)

p ( 15 , 5 ) = 6 + p ( 10 , 3 ) + p ( 10 , 4 ) + 7 = p ( 10 , 3 ) + p ( 10 , 4 ) + 13 p(15,5)=6+p(10,3)+p(10,4)+7=p(10,3)+p(10,4)+13

p ( 10 , 3 ) = p ( 7 , 1 ) + p ( 7 , 2 ) + p ( 7 , 3 ) = 1 + 3 + p ( 7 , 3 ) = p ( 7 , 3 ) + 4 p(10,3)=p(7,1)+p(7,2)+p(7,3)=1+3+p(7,3)=p(7,3)+4

p ( 7 , 3 ) = p ( 4 , 1 ) + p ( 4 , 2 ) + p ( 4 , 3 ) = 1 + 2 + 1 = 4 p(7,3)=p(4,1)+p(4,2)+p(4,3)=1+2+1=4

p ( 10 , 3 ) = p ( 7 , 3 ) + 4 = 4 + 4 = 8 p(10,3)=p(7,3)+4=4+4=8

p ( 10 , 4 ) = p ( 6 , 1 ) + p ( 6 , 2 ) + p ( 6 , 3 ) + p ( 6 , 4 ) = 1 + 3 + p ( 3 ) + p ( 2 ) = 4 + 3 + 2 = 9 p(10,4)=p(6,1)+p(6,2)+p(6,3)+p(6,4)=1+3+p(3)+p(2)=4+3+2=9

p ( 15 , 5 ) = p ( 10 , 3 ) + p ( 10 , 4 ) + 13 = 8 + 9 + 13 = 30 p(15,5)=p(10,3)+p(10,4)+13=8+9+13=30

Thus, there are 30 \boxed{30} ways to distribute the 15 marbles into 5 non-empty group.

3 Helpful 0 Interesting 0 Brilliant 0 Confused

a+b+c+d+e=15, give -1 to each variable on left and use stripes-bars method (I dont know what you say) and then get the answer as 14C4=1001. Why is this wrong?

Prince Loomba - 4 years, 7 months ago

Log in to reply

This would be the answer if each group of marbles was going to a specific person or place. For the sake of this problem, the groups are identical , meaning the order of the groups does not matter.

When the order of groups doesn't matter, the distribution 1 ∣ 2 ∣ 3 ∣ 4 ∣ 5 1|2|3|4|5 is the same as 5 ∣ 4 ∣ 3 ∣ 2 ∣ 1 5|4|3|2|1 and any other permutation of those numbers.

Unfortunately, a stars and bars approach won't work for this problem, because you can't just divide 1001 1001 by 5 ! 5! to get the answer. This is because there's a different number of permutations depending on how many groups are the same size.

1 ∣ 2 ∣ 3 ∣ 4 ∣ 5 5 ! = 120 permutations 2 ∣ 2 ∣ 3 ∣ 3 ∣ 5 ( 5 2 ) ( 3 2 ) ( 1 1 ) = 30 permutations \begin{array}{cc} 1|2|3|4|5 & 5!=120 \text{ permutations} \\ 2|2|3|3|5 & \binom{5}{2}\binom{3}{2}\binom{1}{1}=30 \text{ permutations} \end{array}

This kind of problem, identical objects into identical bins , is deceptively harder than identical objects into distinct bins .

Andy Hayes - 4 years, 7 months ago

Log in to reply

Thanks I did not know this before! Slots different and variables identical for that. Thanks

Prince Loomba - 4 years, 7 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...