The Gateway to Computer Science Excellence
+2 votes
419 views

How many ways are there to place $8$ indistinguishable balls into four distinguishable bins?

  1. $70$
  2. $165$
  3. $^8C_4$
  4. $^8P_4$ 
in Combinatory by Veteran (424k points)
edited by | 419 views
+2
$\binom{11}{3}=165$

2 Answers

+3 votes

$8$ indistinguishable(identical) balls into $4$ distinguishable(distinct) bins.

There are could be empty bins.

 


Using Stars and Bars, we can correlate the indistinguishable(identical) balls into stars and  $4$ distinguishable(distinct) bins into bars.

$8$  indistinguishable(identical) balls like $8$ stars ${\color{Green}{  \bigstar \ \bigstar \ \bigstar \ \bigstar \ \bigstar \ \bigstar \ \bigstar \ \bigstar \ \ } }$

separate $8$ stars into $4$ distinguishable(distinct) bins we can do like this 

 ${\color{Green}{\bigstar}} \ {\color{Blue}{\mid}} \ {\color{Green}{\bigstar \bigstar}} \ {\color{Magenta}{\mid}} \ {\color{Green}{\bigstar\bigstar}} \ {\color{DarkOrange}{\mid}} \ {\color{Green}{\bigstar\bigstar\bigstar}}$ so we need three bars.

There are $8 + 3 = 11$ things, that needs to be placed and $3$ of those placements are chosen for the bars.

Thus, there are $\binom{11}{3} = 165$ possible distribution.

  • Suppose there are $n$ identical objects to be distributed among $r$ distinct bins. This can be done in precisely $\binom{n+r-1}{r-1}$ ways.

References:

by Veteran (54.8k points)
edited by
+1
second image is not required
0
Okay, I will remove them.
+2 votes

Correct answer is option 2. 


Detailed explanation is provided in the pic below:


For case b in the picture above i.e. number of balls m <= number of bags n , it is assumed that one bag cannot contain more than one ball. In that case number of ways will be nCm.

But if the question says that a bag can contain any number of balls, then number of ways will become (n+m-1)Cm.

It must be mentioned in the question. According to the question it must be decided.

 

by Active (1.3k points)
edited by
0
use formula (n+r-1)Cr, where n=3 and r=8
0

@SuvasishDutta

Can u please explain why the number of ways m balls can be placed in n boxes where m<=n is nCm??

0

@Doraemon ,

First of all here balls are indistinguishable. Let us consider the scenario where we have two indistinguishabe balls and number of distinguishable bags are 3 i.e. m=2 and n=3.

Note: Since number of balls are less than number of bags, i have assumed that no bag can contain more than one ball. There can be another case where a bag can contain more than one ball.

But if number of balls are greater than number of bags, then definitely a bag must contain more than one ball.

Thus there are 3 ways in which 2 bags can be selected out of 3 bags. They are (bag1,bag2) , (bag1,bag3), (bag2,bag3).

Let us consider the case of (bag1, bag2). There is only one way in which two balls can be placed in these bags. Why?

There are two possibilities:

1. Placing 1st ball in bag1 and 2nd ball in bag2. 

2. Placing 1st ball in bag2 and 2nd ball in bag1.

Both these possibilities are same since balls are indistinguishable. (B,B) and (B,B) are same where B denotes ball.

Number of possibilities for placing m indistinguishable balls in n distinguishable bags considering no bag can contain more than one ball= nCm

 

+1

@SuvasishDutta

Here we have 2 balls and 3 boxes.

Case 1:Now we could place 2 balls in  1 box and keep the other 3 empty then it is->3C1 ways we could choose a box.

Case 2:Next 1 ball in one box and 2nd ball in another we could choose the box in ->3C2 ways so a total of 

3C1+3C2 way we could actually place it.

 

Why are u not considering Case 1?

 

0
It must be mentioned in the question. It is no the case that always case1 is followed or always case2 is followed. According to the question, which case is followed must be decided.

If the question says that repetition is allowed and number of balls ,m is less than or equal to number of bags,n then-

Number of ways will be (n+m-1)Cm.

In the above example, m=2 and n=3

No of ways= (2+3-1)C2 = 4C2 = 6
0

I have added this to the answer too. Thanks @Doraemon

0

@SuvasishDutta

So in conclusion we could say that for m balls and  n bags with no restriction on the number of balls in a bag  .

For both the cases either m>=n or m<n the formula is  m+n-1Cm right?

0
Yes
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,647 questions
56,492 answers
195,439 comments
100,706 users