[Math] How many ways are there to distribute 5 balls into 3 boxes, under additional conditions

combinatorics

How many ways are there to distribute 5 balls into 3 boxes if:

  1. both the boxes and balls are labeled

  2. the balls are labeled but the boxes are not

  3. the balls are unlabeled but the boxes are labeled

  4. both the balls and boxes are unlabeled

My way of doing these is as follows:

  1. $3^5$?

  2. $C(5,5)$?

  3. $3!5! – C(5,5)$?

  4. $C(3,5)$?

Where $C(k,n)$ means $\binom{n}{k}$.

Best Answer

1) Your answer is correct; for each ball, you can choose any box, and every choice is distinguishable at any time.

2) You want to distribute your 5 distinguishable balls into 3 indistinguishable boxes. Let $B(5,3)$ denote the number of ways in which this can be done into exactly 3 indistinguishable non-empty boxes, and use the recurrence relation $B(n,k)=B(n-1,k-1)+kB(n-1,k)$ with $B(n,1)=1$ and $B(n,n)=1$. You seek $B(5,1)+B(5,2)+B(5,3)$. For further reference, see Stirling number.

3) You want to separate your 5 indistinguishable balls into 3 distinguishable boxes. Note that every admissible separation uniquely corresponds to a permutation of the string $XXbbbbb$.

4) You want to partition your 5 indistinguishable balls into 3 indistinguishable boxes. Let $p(5,3)$ denote the number of ways in which this can be done into exactly 3 indistinguishable non-empty boxes, and use the recurrence relation $p(n,k)=p(n-1,k-1)+p(n-k,k)$ with $p(n,1)=1$ and $p(n,n)=1$. You seek $p(5,1)+p(5,2)+p(5,3)$. For further reference, see partition.

Related Question